[关键字]：随机化算法 模拟退火
[题目大意]：http://221.192.240.123:8586/JudgeOnline/showproblem?problem_id=1677
//======================================================================================================================================================
[分析]：本来还想把它独立做出来，结果碰着这么一道“RP完全问题”，在冥思苦想了几个小时的搜索、贪心、动态规划都无果后，终于放弃了。看完题解发现居然是一道模拟退火的题。先用搜索找出第三类点所有可能的分类，然后对每一类先随便找一个A、B机器的执行序列，然后随机A中的两个点交换顺序，在随机B中的两个点交换顺序，看是否更优如果更优就保存当前顺序并继续执行否则退回上一顺序，大概执行2000多次后，就有很大几率得到最优解（看RP当然也有概率分析）。
[代码]：
View Code #include#include #include #include #include #include #include using namespace std; #define MAXN 100 #define INF 1000000 int N,top1,topa,topb,ans=INF; int c[MAXN],a[MAXN],b[MAXN]; int s1[MAXN],sa[MAXN],sb[MAXN],ssa[MAXN],ssb[MAXN]; bool cmp1(int A,int B) { if (b[A]>b[B]||(b[A]==b[B]&&a[A]<=a[B]))return true; else return false; } bool cmp2(int A,int B) { if (a[A]>a[B]||(a[A]==a[B]&&b[A]<=b[B]))return true; else return false; } void Solve() { topa=topb=0; int ta=0,tb=0; for (int i=1;i<=N;i++) if (c[i]==1) sa[++topa]=i,ta+=a[i]; else sb[++topb]=i,tb+=b[i]; sort(sa+1,sa+topa+1,cmp1); sort(sb+1,sb+topb+1,cmp2); int t1=ta,t2=tb; int Max=INF,v1,v2; for (int i=1;i<=2000;i++) { ta=t1,memcpy(ssa,sa,sizeof(sa)); tb=t2,memcpy(ssb,sb,sizeof(sb)); if (topa) v1=rand()%topa+1,v2=rand()%topa+1,swap(sa[v1],sa[v2]); if (topb) v1=rand()%topb+1,v2=rand()%topb+1,swap(sb[v1],sb[v2]); int temp=0; for (int j=1;j<=topa;j++) { temp+=a[sa[j]]; tb=max(temp,tb)+b[sa[j]]; } temp=0; for (int j=1;j<=topb;j++) { temp+=b[sb[j]]; ta=max(temp,ta)+a[sb[j]]; } temp=max(ta,tb); if (temp>Max) memcpy(sa,ssa,sizeof(sa)),memcpy(sb,ssb,sizeof(sb)); ans=min(temp,ans); Max=min(Max,temp); } } void Dfs(int k) { if (k>top1) { Solve(); return ; } int limit=20000; c[s1[k]]=1; if (rand()%32767