有一个源S，连支持的人。
有一个汇T，连反对的人。
朋友间相互连边。
形成一个图。
现在问最少去多少边可以使S与T不连通。
与S连通的表示他们支持。
与T连通的表示他们反对。
可以用最小割做。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-20
DESCRIPTION:
网络流 乱做
http://acm.hnu.cn/online/?action=problem&type=show&id=10940
*/
#include <stdio.h>
#include <string.h>
const int oo=(~0u)>>1;
const int MAXV=1000000;
const int MAXE=1000000;
typedef struct struct_edge* edge;
struct struct_edge{int v,c;edge n,b;};
struct_edge pool[MAXE];
edge top;
int S,T,V;
edge adj[MAXV];
int d[MAXV];
int q[MAXV];
int head,tail;
void add_edge(int u,int v,int c)
{
top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;
top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;
adj[u]->b=adj[v],adj[v]->b=adj[u];
}
bool relabel()
{
for (int i=0;i<V;d[i++]=oo) ;
d[q[head=tail=0]=T]=0;
while (head<=tail)
{
int u=q[head++];
for (edge i=adj[u];i;i=i->n)
if (i->b->c&&d[i->v]==oo)
d[q[++tail]=i->v]=d[u]+1;
if (d[S]!=oo) return true;
}
return false;
}
int augment(int u,int e)
{
if (u==T) return e;
int f=0;
for (edge i=adj[u];i&&e;i=i->n)
if (i->c&&d[u]==d[i->v]+1)
if (int df=augment(i->v,e<i->c?e:i->c))
i->c-=df,i->b->c+=df,e-=df,f+=df;
return f;
}
int dinic()
{
int f=0;
while (relabel()) f+=augment(S,oo);
return f;
}
int n,m,a,b;
int main()
{
for (;;)
{
scanf(“%d%d”,&n,&m);
if (!n&&!m) break;
top=pool;
memset(adj,0,sizeof(adj));
S=0,T=n+1,V=n+2;
for (int i=1;i<=n;i++)
scanf(“%d”,&a),a?add_edge(S,i,1):add_edge(i,T,1);
for (int i=0;i<m;i++)
scanf(“%d%d”,&a,&b),add_edge(a,b,1),add_edge(b,a,1);
printf(“%d\n”,dinic());
}
}