一个疑问
查看原帖
一个疑问
256970
xie_lzh楼主2021/10/9 12:04

为什么大部分题解在连接超级源点和汇点是不连双向边但我不连就会WA飞

#include<bits/stdc++.h>
using namespace std;
const int N=305,M=45000;
int n,m,s=0,t,u,v,ans;
int read()
{
	int r=0;
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) 
	{
		r=(r<<1)+(r<<3)+c-48;
		c=getchar();
	}
	return r;
}
int head[N],to[N+(M<<1)],nxt[N+(M<<1)],val[N+(M<<1)],cnt=1;
void add(int u,int v,int w)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	val[cnt]=w;
	head[u]=cnt;
}
int dep[N];
bool bfs()
{
	memset(dep,0,sizeof dep);
	queue<int> q;
	q.push(s);
	dep[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(dep[v]>0) continue;
			if(val[i]==0) continue;
			dep[v]=dep[u]+1;
			q.push(v);
		}
	}
	if(dep[t]>0) return true;
	return false;
}
int dfs(int now,int flow)
{
	if(now==t) return flow;
	int nans=0;
	for(int i=head[now];i;i=nxt[i])
	{
		int v=to[i];
		if(dep[v]!=dep[now]+1) continue;
		if(val[i]==0) continue;
		int res=dfs(v,min(val[i],flow));
		if(res==0) continue;
		val[i]-=res;
		val[i^1]+=res;
		nans+=res;
		flow-=res;
		if(flow==0) break;
	}
	if(flow==0) dep[now]=-1;
	return nans;
}
int main()
{
	n=read(); m=read();
	t=n+1;
	for(int i=1;i<=n;i++)
	{
		u=read();
		if(u==1)
		{
			add(s,i,1);
			add(i,s,0);
		}
		else
		{
			add(i,t,1);
			add(t,i,0);
		}
	}
	for(int i=1;i<=m;i++)
	{
		u=read(); v=read();
		add(u,v,1);
		add(v,u,1);
	}
	while(bfs())
	{
		ans+=dfs(s,2e9);
	}
	cout<<ans;
}
2021/10/9 12:04
加载中...