这题给的一个教训：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[][][];
int G[][],from[];
int n,m,res,id,k,w;
int vis[],len[]; struct Ans
{
int ind,pre;
}ans[]; int min(int ka,int kb)
{
if(ka < kb)
return ka;
return kb;
} int dif(char a[][],char b[][])
{
int cnt = ;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(a[i][j] != b[i][j])
cnt++;
}
}
return cnt;
} void Prim()
{
int i,j,tag,mini;
res = ;
id = ;
memset(vis,,sizeof(vis));
memset(from,,sizeof(from));
for(i=;i<=k;i++)
len[i] = n*m; //最大为n*m
for(i=;i<=k;i++)
{
mini = Mod;
for(j=;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 = ;
else
ans[id].ind = tag,ans[id++].pre = from[tag];
vis[tag] = ;
for(j=;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 = ;
for(i=;i<=k;i++)
{
for(j=;j<n;j++)
scanf("%s",mp[i][j]);
}
int T = n*m;
for(i=;i<=k;i++)
{
for(j=i+;j<=k;j++)
G[j][i] = G[i][j] = min(dif(mp[i],mp[j])*w,T);
G[i][i] = ;
}
Prim();
printf("%d\n",res);
for(i=;i<id;i++)
printf("%d %d\n",ans[i].ind,ans[i].pre);
}
return ;
}