[Shoi2007]Vote 善意的投票

Time Limit:1000MS  Memory Limit:65536K
Total Submit:59 Accepted:40

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

1

Hint

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

Source

Day2
额。。这个题目显然可以用网络流解决。。但是经Seventh神牛的提醒。。我使用随机化AC了这个。。。
就是随机一个决策出来。。然后把能最大降低冲突数的那个人决策反过来。。不断搞直到局部最优。。
经过测试随机化10次以上会TLE。。3次就可以AC囧。。
Code：

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=300;
using namespace std;
int A[maxn],X[maxn],ans=inf,n,m;
bool E[maxn][maxn]={};
void Random()
{
rep(i,n)X[i]=rand()%2;
while(true)
{
int ch,Min=inf,f=-1;
rep(i,n)
{
ch=0;X[i]^=1;
if(X[i]^A[i])ch++;else ch–;
rep(j,n)if(E[i][j])
{
if(X[i]^X[j])ch++;
else ch–;
}
X[i]^=1;
if(ch<Min){Min=ch;f=i;}
}
if(Min>=0)break;
X[f]^=1;
}
int ret=0;
rep(i,n)
{
if(X[i]^A[i])ret+=2;
rep(j,n)if(E[i][j]&&X[i]^X[j])
ret++;
}
ret/=2;
ans=min(ret,ans);
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;rep(i,n)cin>>A[i];
int s,t;
rep(i,m)
{
scanf("%d%d",&s,&t);–s;–t;
E[s][t]=E[t][s]=true;
}
rep(i,3)Random();
cout<<ans<<endl;
}