中文题面友链 传送门
Haywire
题目描述
Farmer John’s N cows (4 <= N <= 12, N even) have built a primitive system for communicating between pairs of friendly cows by building wires protected by wrappings made of hay.
Each cow has exactly 3 other friends in the barn, and the cows must arrange themselves to occupy N stalls lined up in a row. A wire of length L requires exactly L units of hay to build, so for example if the cows in stalls 4 and 7 are friends, it would take 3 units of hay to construct a wire to connect them.
Assuming every pair of friends must be connected by a separate wire, please determine the minimum possible amount of hay required to build these wires if the cows order themselves in the best possible way.
输入
Line 1: The integer N. FJ’s cows are conveniently numbered 1…N.
Lines 2…1+N: Each line contains three space-separated integers in the range 1…N. Line i+1 contains the numeric identifiers of the three friends of cow i. If cow i is a friend of cow j, then j will also be a friend of i.
输出
Line 1: The minimum total amount of hay required to connect all pairs of friendly cows.
样例输入 Copy
6
6 2 5
1 3 4
4 2 6
5 3 2
4 6 1
1 5 3
样例输出 Copy
17
提示
There are 6 cows. Cow 1 is friends with cows 6, 2, and 5, etc.A best ordering of the cows is 6, 5, 1, 4, 2, 3, which requires only 17 units of hay.
朴素随机数法
数据很小，利用随机数计算每次交换的牛的位置，计算出花费，跑1e6次就可以了。（真玄学） 好像只能是1e6，反正1e5是82，5e5是92，越来越接近正解了
注意计算花费时每两头牛都算了两遍，所以结果需要/2.
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define I_int ll inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=20,mod=1e9+7,tot=1e6; int pos[maxn][maxn],n,a[maxn],tmp[maxn]; void init(){ for(int i=1;i<=n;i++) a[i]=i; } int cul(){ int sum=0; for(int i=1;i<=n;i++) tmp[a[i]]=i; for(int i=1;i<=n;i++) for(int j=1;j<=3;j++) sum+=abs(tmp[pos[a[i]][j]]-i); return sum/2;//计算时每两个牛的距离都算了都两遍 } void AC(){ n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=3;j++) pos[i][j]=read(); init(); int cnt=1; int minn=2e9; while(cnt<=tot){ int l=(rand())%n+1; int r=(rand())%n+1; int t=a[l];a[l]=a[r];a[r]=t; minn=min(minn,cul()); cnt++; } out(minn); } int main(){ AC(); return 0; }
稍加优化的模拟退火
其实本质也是随机数，只是多了一个判断，如果当前解很差的话，就再交换回去。
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define I_int ll inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=20,mod=1e9+7,tot=5e5; int pos[maxn][maxn],n,a[maxn],tmp[maxn]; int minn=1e8; const double s=10000,e=1e-12,c=0.99; //起始温度 终止温度 温度改变速度 void init(){ for(int i=1;i<=n;i++) a[i]=i; } int cul(){ int sum=0; for(int i=1;i<=n;i++) tmp[a[i]]=i; for(int i=1;i<=n;i++) for(int j=1;j<=3;j++) sum+=abs(tmp[pos[a[i]][j]]-i); return sum/2;//计算时每两个牛的距离都算了都两遍 } void SA(int times){ int x,y,t; while(times--){ for(double i=s;i>e;i*=c){ do{ x=rand()%n+1; y=rand()%n+1; }while(x==y); swap(a[x],a[y]); t=cul(); if(minn>=t) minn=t; else if(exp((minn-t)/i)>(double)rand()/RAND_MAX) swap(a[x],a[y]); //当前解很差 恢复此次交换 } } return ; } void AC(){ n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=3;j++) pos[i][j]=read(); init(); SA(160); out(minn); } int main(){ AC(); return 0; }
几率接受的几率是个很玄学的问题,通常情况,设当前温度为 T T ,当前解为 k k ,最优解为 K_{max} K
max
,我们通常用这样一个玄学公式…
exp((k-kmax)/T)<(double)rand()/RAND_MAX
我当初也不知道exp的意义何在,后来发现太妙了!如果不知道exp是啥,可以自己看一下百科,我稍作解释: exp函数在X < 0时, Y 一定为 0 - 1 之间的小数且单调递增,(double)rand()/RAND_MAX也是一个 0 - 1 之间的小数.这样温度越小,接受当前较差解的几率越低.
最后对比一下两种方法的运行结果吧，其实差不了很多~
朴素版本的随机数
稍加优化的模拟退火
还有个正解是状压dp 想想数据这么小确实可以状压做 未完待续
参考资料：
关于模拟退火的学习笔记 - 李有才99NL的博客 - 洛谷博客
题解 P2210 【Haywire】 - Ciyang 的博客 - 洛谷博客
Haywire （随机数大法好）_weixin_43916298的博客-CSDN博客
