题目大意
给一张n个点的无向图，要求给每个点染色0或1，使得每个点的相邻相同颜色点的数量小于等于其度数的一半。
解题分析
没想到什么好的算法，就随机乱搞了。
若某个状态时，一个点的度数为cnt，相邻相同颜色点的数量为x。
定义delta = cnt / 2 - x;
若delta>=0，说明这是一个合法的状态，则接受它。若delta<0，说明这是一个不合法的状态，以exp(delta/T)的概率接受它。
当T越低时，exp(delta/T)的值越小，接受这个不合法的状态的概率则越小。
ps：参数的设置好谜啊。感觉根本不是在模拟退火，而是在瞎搞。
参考程序
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define N 1008
#define M 2000008
#define eps 1e-8
#define LL long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define bitcnt(x) __builtin_popcount(x)
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define repd(x,y,z) for (int x=y;x>=z;x--)
const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/
int n;
int c[N];
vector <int> eg[N];
double rd(){
return rand() % / 10000.0;
}
int main(){
srand(time(NULL));
scanf("%d",&n);
for (int u=;u<n;u++){
int num;
scanf("%d:",&num);
for (int i=;i<=num;i++){
int v;scanf("%d",&v);
eg[u+].push_back(v+);
}
}
clr(c,);
int pp=;
double T=,r=0.999;
while (T > eps){
pp++;
int u = rand() % n + ;
int cnt=,num=;
for (int i=;i<eg[u].size();i++){
int v=eg[u][i];
cnt++;
if (c[u]==c[v]) num++;
}
int delta=cnt/-num;
if (delta< && rd() > exp(delta/T)){
c[u]^=;
}
T = T * r;
}
printf("%d\n",n );
for (int i=;i<=n;i++){
printf("%d %d:",c[i],eg[i].size());
for (int j=;j<eg[i].size();j++) printf(" %d",eg[i][j]-);
printf("\n");
}
}