凭什么??(Dinic版本)
查看原帖
凭什么??(Dinic版本)
188970
Twiter_ln楼主2023/11/3 17:22

这份代码,跑起来65ms这份代码,跑起来65ms,CodeCode by:by: Red_uncle

#include<bits/stdc++.h> // Test on : 66ms by Red_uncle
using namespace std;
int n,m,s,t;
typedef long long ll;
struct node{
	int to;
	ll w;
	int nex;
	
}e[200005];

int cnt=1;
int head[200005];
ll dis[200005];
int now[200005];
int bfs(){
	for(int i=1;i<=n;i++){
		dis[i]=1e18;
	}
	dis[s]=0;
	queue<int> p;
	p.push(s);
	now[s]=head[s];
	while(!p.empty()){
		int top=p.front();
		p.pop();
		for(int i=head[top];i;i=e[i].nex){
			int y=e[i].to;
			
			if(dis[y]>dis[top]+1&&e[i].w>0){
				now[y]=head[y];
				dis[y]=dis[top]+1;
				p.push(y);
				if(y==t){
					return 1;
				}
			}
		}
	}
	return 0;
}
ll dfs(int x,ll sum){
	if(x==t)return sum;
	ll res=0;
	for(int i=now[x];i&&sum>0;i=e[i].nex){
		int y=e[i].to;
		now[x]=i;
		if(dis[y]==dis[x]+1&&e[i].w>0){
			ll k=dfs(y,min(sum,e[i].w));
			e[i].w-=k;
			e[i^1].w+=k;
			sum-=k;
			res+=k;
		}
	}
	return res;
}
inline void add(int u,int v,ll w){
	e[++cnt].nex=head[u];
	e[cnt].to=v;
	e[cnt].w=w;
	head[u]=cnt;
	e[++cnt].nex=head[v];
	e[cnt].to=u;
	e[cnt].w=0;
	head[v]=cnt;
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int x,y;
		ll w;
		cin>>x>>y>>w;
		add(x,y,w);
	}
	ll ans=0;
	while(bfs()){
	//	cout<<1<<" "<<ans<<'\n';
		ans+=dfs(s,1e18);
	}
	cout<<ans;
	
	return 0;
}

而我的码这样↓,却847ms,凭什么....而我的码这样↓,却847ms,凭什么....

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;
const int N = 207;
typedef long long lli;

int n, m, S, T;
int x, y, z;

struct pot{
	int v, nxt;
	lli val;
}E[50*N];
int head[N], tot = 1;
inline void Add_edge(int u, int v, int val) {
	E[++tot].v = v;
	E[tot].val = val;
	E[tot].nxt = head[u];
	head[u] = tot;
}

int dep[N], cur[N];
inline bool bfs() {
	queue <int> q;
	q.push(S);
	memset(dep, 0, sizeof(dep));
	dep[S] = 1;
	
	int u, v;
	while(q.size()) {
		u = q.front();
		q.pop();
		
		for(int i=head[u];i;i=E[i].nxt) {
			v = E[i].v;
			if(dep[v] || !E[i].val) continue;
			dep[v] = dep[u] + 1;
			q.push(v);
			if(v == T) return true;
		}
	}
	return false;
}
inline lli dfs(int u, lli nowflow) {
	if(u == T) return nowflow;
	if(nowflow == 0) return 0;
	
	int v;
	lli sum = 0, f;
	
	for(int i=cur[u];i;i=E[i].nxt) {
		v = E[i].v;
		cur[u] = i;
		if(dep[v] != dep[u]+1 || !E[i].val) continue;
		f = dfs(v, min(E[i].val, nowflow));
		E[i].val -= f;
		E[i^1].val += f;
		sum += f;
		nowflow -= f;
	}
	return sum;
}

void Dinic() {
	lli ans = 0;
	while(bfs()) {
		memcpy(cur, head, sizeof(cur));
		ans += dfs(S, 0x3fffffffffffffff);
	}
	printf("%lld\n", ans);
}

int main() {
	
	scanf("%d%d%d%d", &n, &m, &S, &T);
	for(int i=1;i<=m;++i) {
		scanf("%d%d%d", &x, &y, &z);
		Add_edge(x, y, z);
		Add_edge(y, x, 0);
	}
	
	Dinic();
	
	return 0;
}

(无语子......)

2023/11/3 17:22
加载中...