P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

拿来练网络流的qwq

思路：如果i不同意，连边（i,t,1），否则连边（s,i,1）.好朋友x,y间连边(x,y,1)(y,x,1)，最小割即为答案。每割一条边表示与他的意愿不相符。

#include<bits/stdc++.h>

using namespace std;

const int N=305;

const int inf=1000000007;

int head[N],num_edge=1;

struct edge{

	int nxt,val,to;

}e[N*N*2];

inline void add(int from,int to,int val)

{

	++num_edge;

	e[num_edge].nxt=head[from];

	e[num_edge].to=to;

	e[num_edge].val=val;

	head[from]=num_edge;

}

int n,m,s,t;

int maxflow,dep[N],cur[N];

bool inq[N];

bool bfs()

{

	for(int i=1;i<=t;++i)

		inq[i]=0,dep[i]=inf,cur[i]=head[i];

	dep[s]=1;

	queue<int>q;

	q.push(s);

	while(!q.empty())

	{

		int u=q.front();q.pop();

		inq[u]=0;

		for(int i=head[u];i;i=e[i].nxt)

		{

			int v=e[i].to;

			if(dep[v]>dep[u]+1&&e[i].val)

			{

				dep[v]=dep[u]+1;

				if(!inq[v])q.push(v),inq[v]=1;

			}

		}

	}

	return dep[t]!=inf;

}

int dfs(int u,int flow)

{

	if(u==t)

	{

		maxflow+=flow;

		return flow;

	}

	int used=0,rlow;

	for(int i=cur[u];i;i=e[i].nxt)

	{

		cur[u]=i;

		int v=e[i].to;

		if(dep[v]==dep[u]+1&&e[i].val)

		{

			rlow=dfs(v,min(flow-used,e[i].val));

			if(rlow)

			{

				used+=rlow;

				e[i].val-=rlow;

				e[i^1].val+=rlow;

				if(used==flow)break;

			}

		}

	}

	return used;

}

void dinic(){while(bfs())dfs(s,inf);}

int main()

{

	scanf("%d%d",&n,&m);s=n+1;t=n+2;

	for(int i=1,x;i<=n;++i)

	{

		scanf("%d",&x);

		if(x==0)add(i,t,1),add(t,i,0);

		if(x==1)add(s,i,1),add(i,s,0);

	}

	for(int i=1,x,y;i<=m;++i)

	{

		scanf("%d%d",&x,&y);

		add(x,y,1);add(y,x,0);

		add(y,x,1);add(x,y,0);

	}

	dinic();

	printf("%d\n",maxflow);

	return 0;

}