这题给的一个教训：Codeforces没有超时这个概念。本来以为1000*(1000+1)/2*10*10要超时的。结果我想多了。
这题由于k层都可能有关系，所以建一个图，每两个点之间连边，边权为n*m和他们之间的差值*w的最小值，然后求一个最小生成树就可以得出结果。且可以证明不会存在环。由于边比较稠密，用Prim算法求最小生成树。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define Mod 1000000007 using namespace std; #define N 2007 char mp[1006][12][12]; int G[1006][1005],from[1006]; int n,m,res,id,k,w; int vis[1005],len[1005]; struct Ans { int ind,pre; }ans[1007]; int min(int ka,int kb) { if(ka < kb) return ka; return kb; } int dif(char a[12][12],char b[12][12]) { int cnt = 0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j] != b[i][j]) cnt++; } } return cnt; } void Prim() { int i,j,tag,mini; res = 0; id = 0; memset(vis,0,sizeof(vis)); memset(from,0,sizeof(from)); for(i=1;i<=k;i++) len[i] = n*m; //最大为n*m for(i=1;i<=k;i++) { mini = Mod; for(j=1;j<=k;j++) { if(!vis[j] && len[j] < mini) { mini = len[j]; tag = j; } } if(mini == Mod) return; res += len[tag]; if(len[tag] == n*m) ans[id].ind = tag,ans[id++].pre = 0; else ans[id].ind = tag,ans[id++].pre = from[tag]; vis[tag] = 1; for(j=1;j<=k;j++) { if(!vis[j] && len[j] > G[tag][j]) { len[j] = G[tag][j]; from[j] = tag; } } } } int main() { int i,j; while(scanf("%d%d%d%d",&n,&m,&k,&w)!=EOF) { id = 0; for(i=1;i<=k;i++) { for(j=0;j<n;j++) scanf("%s",mp[i][j]); } int T = n*m; for(i=1;i<=k;i++) { for(j=i+1;j<=k;j++) G[j][i] = G[i][j] = min(dif(mp[i],mp[j])*w,T); G[i][i] = 0; } Prim(); printf("%d ",res); for(i=0;i<id;i++) printf("%d %d ",ans[i].ind,ans[i].pre); } return 0; }