题解 P2057 【[SHOI2007]善意的投票】

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;
}