ZYCode ICPC Round 随机座位.exe

nfls_old_salty_fish · 2023-12-01 21:42:41 · 个人记录

考虑 n 很小，可以考虑模拟退火,使用floyd计算单次答案。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const long double S=1e6,E=1e-6,V=0.9985;
int n,dis[25][25],anss=1e15,k,ans;
struct edge{
    int u,v;
}e[16]; 
int g[25][25];
int sum;
void init(){
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=g[i][j];
    for(int i=1;i<=n/2;i++)dis[e[i].u][e[i].v]=dis[e[i].v][e[i].u]=3;
}
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
            }
        }
    }
}
long double RAND(){
    int k=rand()%1001;
    return 1.0L*k/1000;
}
void SA(){
    for(long double T=S;T>E;T*=V){
        int pos=rand()%(n/2)+1,pos2=rand()%(n/2)+1;
        int u=e[pos].u,v=e[pos2].v;
        e[pos].u=v,e[pos2].v=u;
        init();
        floyd();
        int sum=0;
        for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)sum+=dis[i][j];
        if(sum<ans||exp((ans-sum)/T)>=RAND())ans=min(ans,sum);
        else e[pos].u=u,e[pos2].v=v;
    }
}
signed main(){
//  freopen("7.in","r",stdin);
//  freopen("10.out","w",stdout);
    srand(time(0));
    cin>>k>>n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        if(i==j)g[i][j]=0;
        else g[i][j]=1e7;
    }
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n/2;j++){
            int u,v;
            cin>>u>>v;
            g[u][v]=k-i+4;
            g[v][u]=k-i+4;
        }
    }
    for(int i=1;i<=n/2;i++)e[i].u=2*i-1,e[i].v=2*i;
    while((double)(clock())/CLOCKS_PER_SEC<1.55){
        ans=1e15;
        SA();
        anss=min(ans,anss);
//      cout<<(double)(clock())/CLOCKS_PER_SEC<<endl;
    }
    cout<<anss+n*(n-1)/2;
    return 0;
}