看到这么奇葩的题目名我笑了，后来这么一个裸的KM调了2小时我哭了……
这是个裸的KM算法，也没什么多说的，主要是注意多组数据时，每次都要把各种数组清空啊，赋值啊什么的，反正比较麻烦。至于为什么调了2小时，在修改标号的时候我修改的是vx和vy……
关于KM的具体理解在另一篇专门的博客里，大家可以搜索一下看看……
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #define N 310
5 #define inf 0xff
6 int a[N][N]={0},n,px[N],py[N],vx[N],vy[N],str[N],fa[N];
7 int find（int now）
8 {
9 int i;
10 if （now==0）
11 return 1;
12 vx[now]=1;
13 for （i=1;i<=n;i++）
14 if （a[now][i]==px[now]+py[i]&&!vy[i]）
15 {
16 vy[i]=1;
17 if （fa[i]==0||find（fa[i]））
18 {
19 fa[i]=now;
20 return 1;
21 }
22 }
23 else
24 if （px[now]+py[i]-a[now][i]<str[i]）
25 str[i]=px[now]+py[i]-a[now][i];
26 return 0;
27 }
28 int KM（）
29 {
30 int i,j,k,x,y,z;
31 for （i=1;i<=n;i++）
32 {
33 for （j=1;j<=n;j++）
34 str[j]=inf;
35 while （1）
36 {
37 memset（vx,0,sizeof（vx））；
38 memset（vy,0,sizeof（vy））；
39 if （find（i））
40 break;
41 k=inf;
42 for （x=1;x<=n;x++）
43 if （！vy[x]&&k>str[x]）
44 k=str[x];
45 for （x=1;x<=n;x++）
46 {
47 if （vx[x]）
48 px[x]-=k;
49 if （vy[x]）
50 py[x]+=k;
51 else
52 str[x]-=k;
53 }
54 }
55 }
56 z=0;
57 for （i=1;i<=n;i++）
58 z+=a[fa[i]][i];
59 return z;
60 }
61 int main（）
62 {
63 int i,j,k,x,y,z;
64 while（scanf（"%d",&n）！=EOF）
65 {
66 memset（px,0,sizeof（px））；
67 memset（py,0,sizeof（py））；
68 memset（fa,0,sizeof（fa））；
69 for （i=1;i<=n;i++）
70 for （j=1;j<=n;j++）
71 {
72 scanf（"%d",&x）；
73 a[i][j]=x;
74 if （x>px[i]）
75 px[i]=x;
76 }
77 printf（"%d\n",KM（））；
78 }
79 }