[UOJ#404][CTSC2018]组合数问题(79分,提交答案题,模拟退火+匈牙利+DP)

1、4、5、6、10都是op=1的点，除4外直接通过模拟退火调参可以全部通过。

 #include<cmath>

 #include<ctime>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=;

 int n,m,K,op,ans,u,v,t[N][N],r[N][N],pos[N];

 struct E{ int u,v; }e[N];

 int sj(int l,int r){ return rand()%(r-l+)+l; }

 double Rand(){ return sj(,)/.; }

 int calc(){

     int res=;

     rep(i,,n) res+=t[i][pos[i]];

     rep(i,,m) res+=r[pos[e[i].u]][pos[e[i].v]];

     return res;

 }

 void SA(){

     for (double T=1e30; T>0.001; T*=0.99997){

         int p=sj(,n),q=sj(,K),ans1=ans-t[p][pos[p]]+t[p][q];

         rep(i,,m){

             if (e[i].u==p) ans1=ans1-r[pos[p]][pos[e[i].v]]+r[q][pos[e[i].v]];

             if (e[i].v==p) ans1=ans1-r[pos[e[i].u]][pos[p]]+r[pos[e[i].u]][q];

         }

         int delta=ans-ans1;

         if (delta> || Rand()<exp(delta/T)) ans=ans1,pos[p]=q;

     }

     rep(i,,){

         int p=sj(,n),q=sj(,K),ans1=ans-t[p][pos[p]]+t[p][q];

         rep(i,,m){

             if (e[i].u==p) ans1=ans1-r[pos[p]][pos[e[i].v]]+r[q][pos[e[i].v]];

             if (e[i].v==p) ans1=ans1-r[pos[e[i].u]][pos[p]]+r[pos[e[i].u]][q];

         }

         if (ans>ans1) ans=ans1,pos[p]=q;

     }

 }

 int main(){

     freopen("placement5.in","r",stdin);

     freopen("placement5.out","w",stdout);

     srand(time());

     scanf("%d%d%d%d",&n,&m,&K,&op);

     rep(i,,m) scanf("%d%d",&u,&v),e[i]=(E){u,v};

     rep(i,,n) rep(j,,K) scanf("%d",&t[i][j]);

     rep(i,,K) rep(j,,K) scanf("%d",&r[i][j]);

     rep(i,,n) pos[i]=; ans=calc(); SA();

     rep(i,,n) printf("%d ",pos[i]); puts("");

     return ;

 }

4号点是[1,133],[134,266],[267,399]三条链，做三次同样的DP即可。

 #include<cmath>

 #include<ctime>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=,inf=1e9;

 int n,m,K,op,ans,id,u,v,t[N][N],r[N][N],pre[N][N],f[N][N];

 void Print(int l,int i,int j){ if (i>l) Print(l,i-,pre[i][j]); printf("%d ",j); }

 int main(){

     freopen("placement4.in","r",stdin);

     freopen("placement4.out","w",stdout);

     srand(time());

     scanf("%d%d%d%d",&n,&m,&K,&op);

     rep(i,,m) scanf("%d%d",&u,&v);

     rep(i,,n) rep(j,,K) scanf("%d",&t[i][j]);

     rep(i,,K) rep(j,,K) scanf("%d",&r[i][j]);

     rep(i,,n) rep(j,,K) f[i][j]=inf;

     rep(i,,) rep(j,,K)

         rep(k,,K){

             int s=f[i-][k]+r[k][j]+t[i][j];

             if (s<f[i][j]) f[i][j]=s,pre[i][j]=k;

         }

     ans=inf;

     rep(i,,K) if (f[][i]<ans) ans=f[][i],id=i;

     Print(,,id);

     rep(i,,K) f[][i]=t[][i];

     rep(i,,) rep(j,,K)

         rep(k,,K){

             int s=f[i-][k]+r[k][j]+t[i][j];

             if (s<f[i][j]) f[i][j]=s,pre[i][j]=k;

         }

     ans=inf;

     rep(i,,K) if (f[][i]<ans) ans=f[][i],id=i;

     Print(,,id);

     rep(i,,K) f[][i]=t[][i];

     rep(i,,) rep(j,,K)

         rep(k,,K){

             int s=f[i-][k]+r[k][j]+t[i][j];

             if (s<f[i][j]) f[i][j]=s,pre[i][j]=k;

         }

     ans=inf;

     rep(i,,K) if (f[][i]<ans) ans=f[][i],id=i;

     Print(,,id);

     return ;

 }

2、3、8、9同样可以用模拟退火做，发现题目给的simulator会创建一个rex.txt来存放op=2时的答案，于是直接用它做估价函数即可。这样第二个点可以得到满分，第3个点可以得到3分，第8个点可以得到1分，第9个点可以得到5分。

 #include<cmath>

 #include<ctime>

 #include<cstdio>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=;

 int n,m,K,op,ans,u,v,t[N][N],r[N][N],pos[N];

 struct E{ int u,v; }e[N*N];

 int sj(int l,int r){ return rand()%(r-l+)+l; }

 double Rand(){ return sj(,)/.; }

 int calc(){

     freopen("placement9.out","w",stdout);

     rep(i,,n) printf("%d ",pos[i]); puts("");

     fclose(stdout);

     system("./simulator placement9.in placement9.out");

     freopen("res.txt","r",stdin);

     int res; scanf("%d",&res); fclose(stdin); return res;

 }

 void SA(){

     for (double T=1e10; T>0.001; T*=0.997,cerr<<T<<endl){

         int p=sj(,n),q=sj(,K),w=pos[p]; pos[p]=q;

         int ans1=calc(),delta=ans-ans1;

         if (delta> || Rand()<exp(delta/T)) ans=ans1; else pos[p]=w;

     }

     rep(i,,){

         int p=sj(,n),q=sj(,K),w=pos[p]; pos[p]=q;

         int ans1=calc();

         if (ans>ans1) ans=ans1; else pos[p]=w;

     }

 }

 int main(){

     freopen("placement9.in","r",stdin);

     srand(time());

     scanf("%d%d%d%d",&n,&m,&K,&op);

     rep(i,,m) scanf("%d%d",&u,&v),e[i]=(E){u,v};

     rep(i,,n) rep(j,,K) scanf("%d",&t[i][j]);

     rep(i,,K) rep(j,,K) scanf("%d",&r[i][j]);

     rep(i,,n) pos[i]=; ans=calc(); SA();

     freopen("placement9.out","w",stdout);

     rep(i,,n) printf("%d ",pos[i]); puts("");

     return ;

 }

7号点可以直接跑匈牙利得到结果。

 #include<cmath>

 #include<ctime>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=;

 int n,m,K,op,u,v,vis[N],lnk[N],ans[N],t[N][N],r[N][N],pos[N];

 bool work(int x,int p){

     rep(i,,K) if (t[x][i]<= && vis[i]!=p){

         vis[i]=p;

         if (lnk[i]==- || work(lnk[i],p)){ lnk[i]=x; return ; }

     }

     return ;

 }

 int main(){

     freopen("placement7.in","r",stdin);

     freopen("placement7.out","w",stdout);

     srand(time());

     scanf("%d%d%d%d",&n,&m,&K,&op);

     rep(i,,m) scanf("%d%d",&u,&v);

     rep(i,,n) rep(j,,K) scanf("%d",&t[i][j]);

     rep(i,,K) rep(j,,K) scanf("%d",&r[i][j]);

     rep(i,,K) lnk[i]=-;

     rep(i,,n) work(i,i);

     rep(i,,K) if (~lnk[i]) ans[lnk[i]]=i;

     rep(i,,n) printf("%d ",ans[i]);

     return ;

 }