bzoj 1934: [Shoi2007]Vote 善意的投票

news/2024/8/26 13:34:14

Description

幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？

Input

第一行只有两个整数n，m，保证有2≤n≤300，1≤m≤n(n-1)/2。其中n代表总人数，m代表好朋友的对数。文件第二行有n个整数，第i个整数代表第i个小朋友的意愿，当它为1时表示同意睡觉，当它为0时表示反对睡觉。接下来文件还有m行，每行有两个整数i，j。表示i，j是一对好朋友，我们保证任何两对i，j不会重复。

Output

只需要输出一个整数，即可能的最小冲突数。

Sample Input

3 3
1 0 0
1 2
1 3
3 2

Sample Output

HINT

在第一个例子中，所有小朋友都投赞成票就能得到最优解

住院了(>A<)我要上学啊！

这题是最小割。S和赞同的人连边，不赞同的人和T连边，朋友互联。然后跑最大流就可以了。

嗯...也就是说。如果一个赞同一个反对则ans必然会+1。。就是这样！【大雾】

#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int head[100001];
struct map
{
	 int f;
	 int s,t;
     int next;
}a[400001];
int b[5001];
int edge;
int p;
int q[400001],d[400001];
inline void add(int s,int t,int f)
{
     a[edge].next=head[s];
     head[s]=edge;
     a[edge].s=s;
     a[edge].t=t;
     a[edge].f=f;
}
inline bool bfs()
{
     int l=0,r=0;
     memset(q,0,sizeof(q));
     r++;
     q[r]=0;
     memset(d,-1,sizeof(d));
     d[0]=0;
     int i,k;
     while(l<r)
     {
     	  l++;
          int k=q[l];
          for(i=head[k];i!=0;i=a[i].next)
          {
               if(a[i].f>0&&d[a[i].t]==-1)
               {
                    d[a[i].t]=d[k]+1;
                    r++;
                    q[r]=a[i].t;
               }
          }
     }
     if(d[p]>=0)
          return true;
     return false;
}
inline int dfs(int k,int s)
{
     if(k==p)
          return s;
     int t=s;
     int i;
     for(i=head[k];i!=0;i=a[i].next)
     {
          if(d[a[i].t]==d[k]+1&&a[i].f>0)
          {
               int xx=dfs(a[i].t,min(s,a[i].f));
               a[i].f-=xx;
               if(i%2==0)
                    a[i-1].f+=xx;
               else
                    a[i+1].f+=xx;
               s-=xx;
          }
     }
     return t-s;
}
inline int maxflow()
{
     int s=0;
     while(bfs())
          s+=dfs(0,2100000000);
     return s;
}
int main()
{
	 int n,m;
	 scanf("%d%d",&n,&m);
	 int i;
	 p=n+1;
	 int x;
	 for(i=1;i<=n;i++)
	 {
	      scanf("%d",&x);
	      if(x==1)
	      {
	           edge++;
	           add(0,i,1);
	           edge++;
	           add(i,0,0);
	      }
	      else
	      {
	           edge++;
	           add(i,p,1);
	           edge++;
	           add(p,i,0);
	      }
	 }
	 int s,t;
	 for(i=1;i<=m;i++)
	 {
	      scanf("%d%d",&s,&t);
	      edge++;
	      add(s,t,1);
	      edge++;
	      add(t,s,1);
	 }
	 printf("%d\n",maxflow());
     return 0;
}