???
查看原帖
???
502247
GTAISHAN楼主2022/12/12 15:27

求助,谢谢

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=205;
const int M=10005;
const int INF=0x3f3f3f3f;
struct edge
{
	int v; 
	ll r;
	int next;
}es[M];
int n,m,s,t,cnt=1;
int flag[N][N];
int head[N];
queue<int> q;
bool vis[N];
int d[N];
int pre[N];
ll ans;
void addedge(int u,int v,int w)
{
	cnt++;
	es[cnt].v=v;
	es[cnt].r=w;
	es[cnt].next=head[u];
	head[u]=cnt;
}
bool bfs()
{
	memset(d,0x3f,sizeof(d));
	q=queue<int>();
	d[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i>0;i=es[i].next)
		{
			int v=es[i].v;
			if(es[i].r>0 && d[v]==INF)
			{
				q.push(v);
				pre[v]=i;
				d[v]=d[u]+1;
				if (v==t) return true;
			}
		}
	}
}
int dfs(int x,ll flow)
{
	if(x==t) return flow;
	ll res=0,tmp;
	for(int i=head[x];i>0&&flow>0;i=es[i].next)
	{
		int v=es[i].v;
		if(es[i].r>0 && d[v]==d[x]+1)
		{
			tmp=dfs(v,min(flow,es[i].r));
			es[i].r-=tmp;
			es[i^1].r+=tmp;
			res+=tmp;
			flow-=tmp;
		}
	}
	return res;
}
int main()
{
	int u,v,w;
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		if(!flag[u][v])
		{
			addedge(u,v,w);
			addedge(v,u,0);
			flag[u][v]=cnt;
		}
		else
		{
			es[flag[u][v]-1].r+=w;
		}
	}
	//Dinic算法 
	while(bfs())
	{
		ans+=dfs(s,INF);
	}
	cout<<ans<<endl;
	return 0;
}
2022/12/12 15:27
加载中...