bzoj1934【shoi2007】Vote善意的投票

Description

Input

Output

Sample Input

Sample Output

HINT

Source

很简单的最小割问题

如果一个同学赞成睡觉，就从源点向他连权值为1的边，否则从他向汇点连权值为1的边。对于一对好朋友，互相连权值为1的边。求出的最小割即为答案。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cmath>
#include<queue>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair<int,int>
#define maxn 310
#define maxm 100000
#define inf 1000000000
using namespace std;
struct edge_type
{
	int next,to,v;
}e[maxm];
int head[maxn],cur[maxn],dis[maxn];
int ans=0,cnt=1,s,t,n,m,x,y;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add_edge(int x,int y,int v1,int v2)
{
	e[++cnt]=(edge_type){head[x],y,v1};head[x]=cnt;
	e[++cnt]=(edge_type){head[y],x,v2};head[y]=cnt;
}
inline bool bfs()
{
	queue<int>q;
	memset(dis,-1,sizeof(dis));
	dis[s]=0;q.push(s);
	while (!q.empty())
	{
		int tmp=q.front();q.pop();
		if (tmp==t) return true;
		for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1)
		{
			dis[e[i].to]=dis[tmp]+1;
			q.push(e[i].to);
		}
	}
	return false;
}
inline int dfs(int x,int f)
{
	if (x==t) return f;
	int tmp,sum=0;
	for(int &i=cur[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if (e[i].v&&dis[y]==dis[x]+1)
		{
			tmp=dfs(y,min(f-sum,e[i].v));
			e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp;
			if (sum==f) return sum;
		}
	}
	return sum;
}
inline void dinic()
{
	while (bfs())
	{
		F(i,1,t) cur[i]=head[i];
		ans+=dfs(s,inf);
	}
}
int main()
{
	n=read();m=read();
	s=n+1;t=s+1;
	F(i,1,n)
	{
		x=read();
		if (x) add_edge(s,i,1,0);
		else add_edge(i,t,1,0);
	}
	F(i,1,m)
	{
		x=read();y=read();
		add_edge(x,y,1,1);
	}
	dinic();
	printf("%d\n",ans);
}

bzoj1934【shoi2007】Vote善意的投票

原文：http://blog.csdn.net/aarongzk/article/details/50405876