dinic求助
查看原帖
dinic求助
181521
珈乐唯毒楼主2020/7/8 09:37

第九个点一直是T的,求大佬救我QAQ

#include<bits/stdc++.h>
using namespace std;
const long long N=205,M=5005,INF=LLONG_MAX;
long long head[N],en=1;
struct Edge{
	long long next,to,from,val;
}edge[M*2];
void add(long long from,long long to,long long val){
	edge[++en].to=to;
	edge[en].next=head[from];
	edge[en].val=val;
	head[from]=en;
	return;
} 
long long n,m,s,t;
long long ans;
long long dep[N];
queue<long long> q;
bool bfs(){
	memset(dep,0,sizeof(dep));
	q.push(s);
	dep[s]=1;
	while(!q.empty()){
		long long u=q.front();
		q.pop();
		for(long long i=head[u];i;i=edge[i].next){
			if(!edge[i].val||dep[edge[i].to])continue;
			long long v=edge[i].to;
			dep[v]=dep[u]+1;
			q.push(v);
		}
	}
	return dep[t]!=0;
}
long long dfs(long long u,long long flow){
	if(u==t)return flow;
	long long ans=0;
	for(long long i=head[u];i;i=edge[i].next){
		if(!edge[i].val||dep[edge[i].to]!=dep[u]+1)continue;
		long long v=edge[i].to;
		long long rst=dfs(v,min(flow-ans,edge[i].val));
		ans+=rst;
		edge[i].val-=rst;
		edge[i^1].val+=rst;
		if(ans==flow)break;
	}
	return ans;
}
long long dinic(){
	long long ans=0;
	while(bfs()){
		long long rst=dfs(s,INF);
		if(!rst)return ans;
		ans+=rst;
	}
	return ans;
}
int main(){
	cin>>n>>m>>s>>t;
	for(long long i=1;i<=m;i++){
		long long u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		add(v,u,0);
		add(u,v,w);
	}
	cout<<dinic();
	return 0;
} 
2020/7/8 09:37
加载中...