1、4、5、6、10都是op=1的点，除4外直接通过模拟退火调参可以全部通过。
1 #include<cmath> 2 #include<ctime> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<algorithm> 6 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 7 using namespace std; 8 9 const int N=5010; 10 int n,m,K,op,ans,u,v,t[N][N],r[N][N],pos[N]; 11 struct E{ int u,v; }e[N]; 12 13 int sj(int l,int r){ return rand()%(r-l+1)+l; } 14 double Rand(){ return sj(0,10000)/10000.; } 15 16 int calc(){ 17 int res=0; 18 rep(i,1,n) res+=t[i][pos[i]]; 19 rep(i,1,m) res+=r[pos[e[i].u]][pos[e[i].v]]; 20 return res; 21 } 22 23 void SA(){ 24 for (double T=1e30; T>0.001; T*=0.99997){ 25 int p=sj(1,n),q=sj(1,K),ans1=ans-t[p][pos[p]]+t[p][q]; 26 rep(i,1,m){ 27 if (e[i].u==p) ans1=ans1-r[pos[p]][pos[e[i].v]]+r[q][pos[e[i].v]]; 28 if (e[i].v==p) ans1=ans1-r[pos[e[i].u]][pos[p]]+r[pos[e[i].u]][q]; 29 } 30 int delta=ans-ans1; 31 if (delta>0 || Rand()<exp(delta/T)) ans=ans1,pos[p]=q; 32 } 33 rep(i,1,1000){ 34 int p=sj(1,n),q=sj(1,K),ans1=ans-t[p][pos[p]]+t[p][q]; 35 rep(i,1,m){ 36 if (e[i].u==p) ans1=ans1-r[pos[p]][pos[e[i].v]]+r[q][pos[e[i].v]]; 37 if (e[i].v==p) ans1=ans1-r[pos[e[i].u]][pos[p]]+r[pos[e[i].u]][q]; 38 } 39 if (ans>ans1) ans=ans1,pos[p]=q; 40 } 41 } 42 43 int main(){ 44 freopen("placement5.in","r",stdin); 45 freopen("placement5.out","w",stdout); 46 srand(time(0)); 47 scanf("%d%d%d%d",&n,&m,&K,&op); 48 rep(i,1,m) scanf("%d%d",&u,&v),e[i]=(E){u,v}; 49 rep(i,1,n) rep(j,1,K) scanf("%d",&t[i][j]); 50 rep(i,1,K) rep(j,1,K) scanf("%d",&r[i][j]); 51 rep(i,1,n) pos[i]=1; ans=calc(); SA(); 52 rep(i,1,n) printf("%d ",pos[i]); puts(""); 53 return 0; 54 }
4号点是[1,133],[134,266],[267,399]三条链，做三次同样的DP即可。
1 #include<cmath> 2 #include<ctime> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<algorithm> 6 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 7 using namespace std; 8 9 const int N=5010,inf=1e9; 10 int n,m,K,op,ans,id,u,v,t[N][N],r[N][N],pre[N][N],f[N][N]; 11 12 void Print(int l,int i,int j){ if (i>l) Print(l,i-1,pre[i][j]); printf("%d ",j); } 13 14 int main(){ 15 freopen("placement4.in","r",stdin); 16 freopen("placement4.out","w",stdout); 17 srand(time(0)); 18 scanf("%d%d%d%d",&n,&m,&K,&op); 19 rep(i,1,m) scanf("%d%d",&u,&v); 20 rep(i,1,n) rep(j,1,K) scanf("%d",&t[i][j]); 21 rep(i,1,K) rep(j,1,K) scanf("%d",&r[i][j]); 22 rep(i,1,n) rep(j,1,K) f[i][j]=inf; 23 rep(i,1,133) rep(j,1,K) 24 rep(k,1,K){ 25 int s=f[i-1][k]+r[k][j]+t[i][j]; 26 if (s<f[i][j]) f[i][j]=s,pre[i][j]=k; 27 } 28 ans=inf; 29 rep(i,1,K) if (f[133][i]<ans) ans=f[133][i],id=i; 30 Print(1,133,id); 31 rep(i,1,K) f[134][i]=t[134][i]; 32 rep(i,134,266) rep(j,1,K) 33 rep(k,1,K){ 34 int s=f[i-1][k]+r[k][j]+t[i][j]; 35 if (s<f[i][j]) f[i][j]=s,pre[i][j]=k; 36 } 37 ans=inf; 38 rep(i,1,K) if (f[266][i]<ans) ans=f[266][i],id=i; 39 Print(134,266,id); 40 rep(i,1,K) f[267][i]=t[267][i]; 41 rep(i,267,399) rep(j,1,K) 42 rep(k,1,K){ 43 int s=f[i-1][k]+r[k][j]+t[i][j]; 44 if (s<f[i][j]) f[i][j]=s,pre[i][j]=k; 45 } 46 ans=inf; 47 rep(i,1,K) if (f[399][i]<ans) ans=f[399][i],id=i; 48 Print(267,399,id); 49 return 0; 50 }
2、3、8、9同样可以用模拟退火做，发现题目给的simulator会创建一个rex.txt来存放op=2时的答案，于是直接用它做估价函数即可。这样第二个点可以得到满分，第3个点可以得到3分，第8个点可以得到1分，第9个点可以得到5分。
1 #include<cmath> 2 #include<ctime> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<iostream> 6 #include<algorithm> 7 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 8 using namespace std; 9 10 const int N=5010; 11 int n,m,K,op,ans,u,v,t[N][N],r[N][N],pos[N]; 12 struct E{ int u,v; }e[N*N]; 13 14 int sj(int l,int r){ return rand()%(r-l+1)+l; } 15 double Rand(){ return sj(0,10000)/10000.; } 16 17 int calc(){ 18 freopen("placement9.out","w",stdout); 19 rep(i,1,n) printf("%d ",pos[i]); puts(""); 20 fclose(stdout); 21 system("./simulator placement9.in placement9.out"); 22 freopen("res.txt","r",stdin); 23 int res; scanf("%d",&res); fclose(stdin); return res; 24 } 25 26 void SA(){ 27 for (double T=1e10; T>0.001; T*=0.997,cerr<<T<<endl){ 28 int p=sj(1,n),q=sj(1,K),w=pos[p]; pos[p]=q; 29 int ans1=calc(),delta=ans-ans1; 30 if (delta>0 || Rand()<exp(delta/T)) ans=ans1; else pos[p]=w; 31 } 32 rep(i,1,1000){ 33 int p=sj(1,n),q=sj(1,K),w=pos[p]; pos[p]=q; 34 int ans1=calc(); 35 if (ans>ans1) ans=ans1; else pos[p]=w; 36 } 37 } 38 39 int main(){ 40 freopen("placement9.in","r",stdin); 41 srand(time(0)); 42 scanf("%d%d%d%d",&n,&m,&K,&op); 43 rep(i,1,m) scanf("%d%d",&u,&v),e[i]=(E){u,v}; 44 rep(i,1,n) rep(j,1,K) scanf("%d",&t[i][j]); 45 rep(i,1,K) rep(j,1,K) scanf("%d",&r[i][j]); 46 rep(i,1,n) pos[i]=1; ans=calc(); SA(); 47 freopen("placement9.out","w",stdout); 48 rep(i,1,n) printf("%d ",pos[i]); puts(""); 49 return 0; 50 }
7号点可以直接跑匈牙利得到结果。
1 #include<cmath> 2 #include<ctime> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<algorithm> 6 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 7 using namespace std; 8 9 const int N=5010; 10 int n,m,K,op,u,v,vis[N],lnk[N],ans[N],t[N][N],r[N][N],pos[N]; 11 12 bool work(int x,int p){ 13 rep(i,1,K) if (t[x][i]<=1014 && vis[i]!=p){ 14 vis[i]=p; 15 if (lnk[i]==-1 || work(lnk[i],p)){ lnk[i]=x; return 1; } 16 } 17 return 0; 18 } 19 20 int main(){ 21 freopen("placement7.in","r",stdin); 22 freopen("placement7.out","w",stdout); 23 srand(time(0)); 24 scanf("%d%d%d%d",&n,&m,&K,&op); 25 rep(i,1,m) scanf("%d%d",&u,&v); 26 rep(i,1,n) rep(j,1,K) scanf("%d",&t[i][j]); 27 rep(i,1,K) rep(j,1,K) scanf("%d",&r[i][j]); 28 rep(i,1,K) lnk[i]=-1; 29 rep(i,1,n) work(i,i); 30 rep(i,1,K) if (~lnk[i]) ans[lnk[i]]=i; 31 rep(i,1,n) printf("%d ",ans[i]); 32 return 0; 33 }