2020/6/26 甚至没有用反向弧也能过
查看原帖
2020/6/26 甚至没有用反向弧也能过
49953
mrchen116楼主2020/6/26 22:26

这组数据我的代码输出1,实际答案是2,但我的代码AC了

6 7 1 6
1 2 1
2 4 1
4 6 1
1 3 1
3 4 1
2 5 1
5 6 1

我的AC代码(无反向弧

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct Eg
{
	int from,to,c;
	Eg(int u,int v,int cc):from(u),to(v),c(cc){}
};
vector<Eg> edge;
vector<int> g[10001];
int n,m,s,t,maxf[10001],pass[10001];
long long ans=0;
void maxflow()
{
	while(1)
	{
		memset(maxf,0,sizeof(maxf));
		memset(pass,0,sizeof(pass));
		queue<int>Q;
		Q.push(s);
		maxf[s]=0x3f3f3f;
		while(!Q.empty())
		{
			int u=Q.front();
			Q.pop();
			for(int i=0;i<g[u].size();i++)
			{
				Eg& e=edge[g[u][i]];
				if(maxf[e.to]==0&&e.c>0)
				{
					pass[e.to]=g[u][i];
					maxf[e.to]=min(maxf[u],e.c);
					Q.push(e.to);
				}
				if(maxf[t])break;
			}	
		}
		if(!maxf[t])break;
		for(int i=t;i!=s;i=edge[pass[i]].from)
		{
			edge[pass[i]].c-=maxf[t];
		//	edge[pass[i]^1].c+=maxf[t];
		}
		ans+=maxf[t];
	}
}
int main()
{
	//freopen("sb.in","r",stdin);
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		edge.push_back(Eg(u,v,w));
		//edge.push_back(Eg(v,u,0));
		int len=edge.size();
		g[u].push_back(len-1);
		//g[v].push_back(len-1);
	}
	maxflow();
	printf("%lld",ans);
	return 0;
}

求加强数据

2020/6/26 22:26
加载中...