MnZn网络流37分求助+样例说明图疑似有误
查看原帖
MnZn网络流37分求助+样例说明图疑似有误
317622
_Ad_Astra_楼主2022/7/24 14:02

RT.

样例图中1~3的flow应该为40,不是30

还有求助37分,TLE一个点WA6个点

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,t,ans,lev[210],cnt,now[210],head[210];
struct node
{
	int to,nxt,flow;
	node(){}
	node(int _to,int _nxt,int _flow)
	{
		to=_to,nxt=_nxt,flow=_flow;
	} 
}g[10010];
void newedge(int u,int v,int flow)
{
	g[++cnt]=node(v,head[u],flow);
	head[u]=cnt;
	g[++cnt]=node(u,head[v],0);
	head[v]=cnt;
}
bool bfs(int s,int t)
{
	for(int i=1;i<=n;i++)lev[i]=inf;
	queue<int>q;
	q.push(s);
	lev[s]=0;
	now[s]=head[s];
	while(!q.empty())
	{
		int u=q.front();q.pop();
		int id=head[u];
		while(id)
		{
			int v=g[id].to;
			if(g[id].flow>0&&lev[v]==inf)
			{
				q.push(v);
				lev[v]=lev[u]+1;
				now[v]=head[v];
				if(v==t)return 1;
			}
			id=g[id].nxt;
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
//	cout<<u<<' '<<flow<<endl;
	if(u==t)return flow;
	int ans=0,id=now[u];
	while(id&&flow)
	{
		now[u]=id;
		int v=g[id].to;
		if(g[id].flow>0&&lev[u]+1==lev[v])
		{
			int pflow=dinic(v,min(flow,g[id].flow));
			if(!pflow)lev[v]=inf;
			g[id].flow-=pflow;
			g[id^1].flow+=pflow;
			ans+=pflow;
			flow-=pflow;
		}
		id=g[id].nxt;
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int u,v,flow;
		cin>>u>>v>>flow;
		newedge(u,v,flow);
	}
//	for(int i=1;i<=cnt;i++)cout<<g[i].to<<" "<<g[i].nxt<<" "<<g[i].flow<<endl;
	while(bfs(s,t))
	{
//		for(int i=1;i<=n;i++)cout<<lev[i]<<" ";
//		cout<<endl;
		ans+=dinic(s,inf);
//		for(int i=1;i<=n;i++)cout<<now[i]<<" ";
//		cout<<endl<<endl; 
	}
	cout<<ans;
	return 0;
}
2022/7/24 14:02
加载中...