Dinic730ms
查看原帖
Dinic730ms
319668
Harukawa楼主2021/11/23 18:45

尝试了若干次,发现速度依然很慢,去看了其他ac的代码,暂且没能发现问题,可能是当前弧优化的问题(??),代码如下,还望不吝赐教

#include <bits/stdc++.h>
#define ll long long
#define rint register int 
#define gc getchar
#define inf 200011230000
#define maxm 12000
#define maxn 400
using namespace std;

inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}

struct Edge{
	ll to,val;
	Edge(ll t=0L,ll v=0L):to(t),val(v){}
}ed[maxm+20];
int he[maxn+20],now[maxn+20],ne[maxm+20],dep[maxn+20],maxint[maxn+20];
int tot=1,n,m,s,t,u,v;
ll w,ans;

void add_edge(int f,int t,ll v){
	ed[++tot]=Edge(t,v);
	ne[tot]=he[f];
	he[f]=tot;
}

bool bfs(int s){
	memcpy(now,he,sizeof(now));
	memcpy(dep,maxint,sizeof(dep));
	queue<int> q;
	q.push(s);
	dep[s]=1;
	while(!q.empty()){
		int tmp=q.front();
		q.pop();
		if(tmp==t) return true;
		for(rint i=he[tmp];i;i=ne[i]){
			if(dep[ed[i].to]==2147483647&&ed[i].val>0){
				dep[ed[i].to]=dep[tmp]+1;
				q.push(ed[i].to);
			}
		}
	}
	return false;
}

ll dfs(int o,ll in){
	if(o==t) return in;
	ll k,out=0;
	for(rint i=now[o];i;i=ne[i]){
		now[o]=i;
		if(dep[ed[i].to]==dep[o]+1&&ed[i].val>0){
			k=dfs(ed[i].to,min(in,ed[i].val));
			ed[i].val-=k;
			ed[i^1].val+=k;
			in-=k;
			out+=k;
			if(ed[i].val==0) dep[ed[i].to]=2147483647;
		}
	}
	return out;
}

int main(){
	cin>>n>>m>>s>>t;
	for(rint i=0;i<maxn;i++) maxint[i]=2147483647;
	for(rint i=1;i<=m;i++){
		u=read();
		v=read();
		w=read();
		add_edge(u,v,w);
		add_edge(v,u,0L);
	}
	while(bfs(s)) ans+=dfs(s,inf);
	cout<<ans;
	return 0;
}


2021/11/23 18:45
加载中...