萌新求助可行流当前弧优化
  • 板块学术版
  • 楼主Harry27182SDream
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/12/10 10:25
  • 上次更新2023/11/3 22:35:48
查看原帖
萌新求助可行流当前弧优化
376997
Harry27182SDream楼主2021/12/10 10:25

rt,为什么cut[u]=i是对的,cur[u]=e[i].nxt就是错的啊/kel

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct edge
{
	int v,w,nxt;
}e[20805];
struct node
{
	int u,v,minw,maxw;
}E[10205];
int h[205],dis[205],cur[205],in[205],out[205],n,m,s,t,ans,cnt,sum;
void add(int u,int v,int w)
{
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=h[u];
	h[u]=cnt++;
}
bool bfs()
{
	for(int i=1;i<=n+2;i++)dis[i]=-1;
	dis[s]=0;
	queue<int>q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i!=-1;i=e[i].nxt)
		{
			int v=e[i].v;
			if(dis[v]==-1&&e[i].w)
			{
				dis[v]=dis[u]+1;
				q.push(v);
			}
		}
	}
	return dis[t]!=-1;
}
int dfs(int u,int flow)
{
	if(u==t)return flow;
	int rest=flow;
	for(int i=cur[u];i!=-1;i=e[i].nxt)
	{
		cur[u]=i;//这是对的 
		//cur[u]=e[i].nxt 这是错的 
		int v=e[i].v;
		if(dis[v]==dis[u]+1&&e[i].w)
		{
			int d=dfs(v,min(rest,e[i].w));
			e[i].w-=d;e[i^1].w+=d;
			rest-=d;
			if(!rest)break;
		}
	}
	return flow-rest;
}
signed main()
{
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof(h));
	s=n+1;t=n+2;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].minw,&E[i].maxw);
		in[E[i].v]+=E[i].minw;
		out[E[i].u]+=E[i].minw;
		add(E[i].u,E[i].v,E[i].maxw-E[i].minw);
		add(E[i].v,E[i].u,0);
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]>=out[i])
		{
			add(s,i,in[i]-out[i]);
			add(i,s,0);
			sum+=in[i]-out[i];
		}
		else
		{
			add(i,t,out[i]-in[i]);
			add(t,i,0);
		}
	}
	while(bfs())
	{
		for(int i=1;i<=n+2;i++)cur[i]=h[i];
		ans+=dfs(s,inf);
	}
	if(ans!=sum)printf("NO");
	else 
	{
		printf("YES\n");
		for(int i=1;i<=2*m;i+=2)printf("%d\n",E[i/2+1].minw+e[i].w);
	}
	return 0;
}
2021/12/10 10:25
加载中...