题解 P2057 【[SHOI2007]善意的投票】
ChthollyTree
2018-11-02 21:05:09
其实这题模拟退火也能过。
模拟退火，一般用于求最优值的问题，
首先设定一个初始温度，在高温状态比较容易接受不是最优解，之后温度降低，较为难接受不优解
这题也是这样
```
#include<bits/stdc++.h>
using namespace std;
#define MAXN 305
#define db double
struct aa
{
int x,y,ls;
}b[MAXN*MAXN*2];
int cnt,t[MAXN];
int n,m,ans;
int a[MAXN],d;
bool c[MAXN];
void jb(int x,int y)//建边
{
cnt ++;
b[cnt].x = x;
b[cnt].y = y;
b[cnt].ls = t[x];
t[x] = cnt;
}
void rd()//输入
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i ++)
cin >> a[i];
for(int i = 1; i <= m; i ++)
{
int x,y;
scanf("%d%d",&x,&y);
jb(x,y);
jb(y,x);
}
}
db sj()
{
return ((db)(rand()*rand()%19260817))/(db)19260817;
}
void mnth(db s,db dt,db tt)//s:现在温度，dt每次降温，tt最终温度，d表示现在
{
for(s;s >= tt; s *= dt)
{
int x = rand()%n+1,ls =d;
c[x] = !c[x];//改变一个人的选票
if(c[x] == a[x]) d -= 1;
else d += 1;//和自己意向不同
for(int i = t[x]; i != 0; i = b[i].ls)
if(c[x] == c[b[i].y]) d -= 1;
else d += 1;//和朋友选票不同
ans = min(ans,d);
if(d < ls || exp((d-ls)/s) < sj()*10)
{
;
}
else
{
c[x] = !c[x];
d = ls;
}
}
for(int i = 1; i <= 233; i ++)
{
int x = rand()%n+1,ls =d;
c[x] = !c[x];
if(c[x] == a[x]) d -= 1;
else d += 1;
for(int i = t[x]; i != 0; i = b[i].ls)
if(c[x] == c[b[i].y]) d -= 1;
else d += 1;
ans = min(ans,d);
if(d < ls)
{
;
}
else
{
c[x] = !c[x];
d = ls;
}
}
}
int main()
{
rd();
for(int i = 1; i <= n; i ++)
if(a[i] != 0)
ans ++;
d = ans;
mnth(1000000000,0.9997,0.0000001);
if(n < 100)
{
mnth(1000000000,0.99997,0.0000001);
}
cout<<ans;
return 0;
}
```