solution-uva1389

lsw1 · 2022-08-11 12:29:30 · 题解

像这种题，模拟退火理论上都能做。

状态为裁掉那些人，能量值直接按题目给的计算。初始状态设为裁掉所有人，能量值自然为 \frac{m}{n} 。

注意得到新状态时，建议用旧状态随机改变一个点的状态，否则可能因一次转移花费时间过长导致退火次数不够多，进而导致答案错误。

采用这种写法的，建议初温设为 10^7 ，终温设为 10^{-14} ，降温系数设为 0.99 ，然后套上模拟退火板子就可以了。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <ctime>
#include <cmath>
using namespace std;
const double EPS = 1e-14;
const int MAXN = 1e2;
vector<int>graph[MAXN + 5];
int n,m;
bool lst[MAXN + 5],cur[MAXN + 5];//lst是答案，cur是当前状态
double ans,curx,cury;
double f(int u,bool flag,int &x,int &y)//计算能量值，u表示更改哪个点，flag表示改为什么，x和y直接引用，计算能量分子分母
{//当然要是你想要pair<double,pair<int,int> >f(int u,bool flag)也行
//记录分子分母是为了快速转移
    if(flag)
    {
        y++;
        for(int i = 0;i < graph[u].size();i++)
        {
            int v = graph[u][i];
            if(cur[v])
            {
                x++;
            }
        }
    }
    else
    {
        if(y == 1)
        {
            return -1;
        }
        y--;
        for(int i = 0;i < graph[u].size();i++)
        {
            int v = graph[u][i];
            if(cur[v])
            {
                x--;
            }
        }
    }
    return x * 1.0 / y;
}
double rand_()
{
    return (double)rand() / RAND_MAX;
}
void SA()
{
    double tpt = 1e7;
    while(tpt > EPS)
    {
        int x = rand() % n + 1,tmpx = curx,tmpy = cury;//在旧状态的基础上转移得到新状态，否则难以通过此题
        bool tmp = cur[x];
        double cura = f(x,!tmp,tmpx,tmpy),delta = cura - ans;
        if(delta > 0)
        {
            cur[x] = !tmp;
            curx = tmpx;
            cury = tmpy;
            ans = cura;
            memcpy(lst,cur,sizeof(lst));
        }
        else if(exp(delta / tpt) > rand_())
        {
            cur[x] = !tmp;
            curx = tmpx;
            cury = tmpy;
        }
        tpt *= 0.99;
    }
}
int main()
{
    srand(time(0));
    while(cin >> n >> m)
    {
        if(m == 0)//特判
        {
            cout << "1\n1\n";
            continue;
        }
        for(int i = 1;i <= n;i++)//多测记得要清空
        {
            graph[i].clear();
        }
        for(int i = 1;i <= m;i++)
        {
            int u,v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        memset(lst,true,sizeof(lst));//初始状态设为全部裁掉
        memset(cur,true,sizeof(cur));
        curx = m;
        cury = n;
        ans = curx * 1.0 / cury;
        for(int i = 1;i <= 60;i++)
        {
            SA();
        }
        int cnt = 0;
        for(int i = 1;i <= n;i++)
        {
            if(lst[i])
            {
                cnt++;
            }
        }
        cout << cnt << endl;
        for(int i = 1;i <= n;i++)
        {
            if(lst[i])
            {
                cout << i << endl;
            }
        }
        cout << endl;
    }
    return 0;
}