Haywire

洛咕

题意:\(Farmer John\)有\(N\)只奶牛,(\(4<=N<=12\),其中\(N\)是偶数).他们建立了一套原生的系统，使得奶牛与他的朋友可以通过由干草保护的线路来进行对话交流.每一头奶牛在这个牧场中正好有3个朋友，并且他们必须把自己安排在一排干草堆中.一条长\(L\)的线路要占用刚好\(L\)堆干草来保护线路.比如说，如果有两头奶牛分别在草堆\(4\)与草堆\(7\)中，并且他们是朋友关系，那么我们就需要用\(3\)堆干草来建造线路，使他们之间能够联系.假设每一对作为朋友的奶牛都必须用一条单独的线来连接，并且我们可以随便地改变奶牛的位置，请计算出我们建造线路所需要的最少的干草堆.

分析:好久没做过黑题了.这题真的好水,模拟退火一遍过的,隔壁[TJOI2010]分金币作为一道紫题调了一下午还是全\(WA\)(至今未过),你谷的评分真的是恶意乱评.

还是老套路,模拟退火随机打乱排列,然后每次\(n^2\)计算当前排列的答案,看是否能够更新即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=15;
int n,ans,a[N],w[N][N];
inline int calc(){
    int cnt=0;
    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
            if(w[a[i]][a[j]])cnt+=j-i;
    return cnt;
}
inline void mnth(){
    double T=2333,eps=1e-10;
    while(T>eps){
        int x=rand()%n+1,y=rand()%n+1;
        if(x==y){T*=0.998;continue;}
        swap(a[x],a[y]);
        int now=calc(),delta=now-ans;
        if(delta<0)ans=now;
        else if(exp(-delta/T)*RAND_MAX>rand())ans=now;
        else swap(a[x],a[y]);
        T*=0.998;
    }
}
int main(){
    srand((int)time(NULL));n=read();
    for(int i=1;i<=n;++i)
        for(int j=1,x;j<=3;++j)x=read(),w[i][x]=1;
    for(int i=1;i<=n;++i)a[i]=i;
    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
            if(w[a[i]][a[j]])ans+=j-i;
    mnth();printf("%d\n",ans);
    return 0;
}

Haywire

原文：https://www.cnblogs.com/PPXppx/p/11673891.html