写了一道HNOI的集训题

写了个模拟退火,怒拿90分

一切在35分钟内做完

PS:似乎写的是错的...

退火的时候应该是-1/温度而不是温度本身..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct edge
{
    int x;
    int y;
    int id;
};
vector<edge> col[55];
int best_ans;
bitset<64> cols;
int n,m;
int father[105],size[105];
int findroot(int x)
{
    int root;
    for (root=x;father[root]!=-1;root=father[root]) ;
    int temp;
    for (;father[x]!=-1;)
    {
        temp=father[x];
        father[x]=root;
        x=temp;
    }
    return root;
}
void u(int x,int y)
{
    x=findroot(x);
    y=findroot(y);
    if (x==y) return;
    if (size[x]>size[y]) swap(x,y);
    size[y]+=size[x];
    father[x]=y;
}
int random()
{
    return (rand()<<15)+rand();
}
void try_best_ans()
{
    double t=273.15;
    bitset<64> now;
    int now_ans=50;
    int i;
    for (i=0;i<50;i++)
    {
        now[i]=true;
    }
    for (;;)
    {
        if (t<=1e-10) return;
        bitset<64> temp=now;
        int i;
        int k=rand()%50;
        temp[k]=!temp[k];
        if (temp[k]==1)
        {
            if (exp(-t)*RAND_MAX*RAND_MAX<random())
            {
                now_ans++;
                now=temp;
            }
            t*=0.999;
            continue;
        }
        for (i=0;i<n;i++)
        {
            father[i]=-1;
            size[i]=1;
        }
        for (i=0;i<50;i++)
        {
            if (temp[i])
            {
                int j;
                for (j=0;j<(int)col[i].size();j++)
                {
                    u(col[i][j].x,col[i][j].y);
                }
            }
        }
        int cnt=0;
        for (i=0;i<n;i++)
        {
            if (father[i]==-1) cnt++;
        }
        if (cnt==1)
        {
            now_ans--;
            now=temp;
            if (now_ans<best_ans)
            {
                best_ans=now_ans;
                cols=now;
            }
        }
        else
        {
            t*=0.999;
        }
    }
}
int main()
{
    freopen("simplest7.in","r",stdin);
    freopen("simplest7.out","w",stdout);
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        x--;
        y--;
        z--;
        edge a;
        a.x=x;
        a.y=y;
        a.id=i;
        col[z].push_back(a);
    }
    best_ans=50;
    for (i=0;i<50;i++)
    {
        cols[i]=true;
    }
    try_best_ans();
    int sum=0;
    for (i=0;i<50;i++)
    {
        if (cols[i])
        {
            int j;
            for (j=0;j<(int)col[i].size();j++)
            {
                sum++;
            }
        }
    }
    printf("%d\n",sum);
    int flag=0;
    for (i=0;i<50;i++)
    {
        if (cols[i])
        {
            int j;
            for (j=0;j<(int)col[i].size();j++)
            {
                if (flag==0) flag=1; else printf(" ");
                printf("%d",col[i][j].id+1);
            }
        }
    }
    printf("\n");
    freopen("log6.txt","w",stdout);
    printf("%d\n",best_ans);
    return 0;
}