题目链接：?pid=2255 题意：中文 //KM算法模板题，，用来测试一下模板 代码：
;const int N = 310;const int INF = 0x3f3f3f3f;int nx, ny;int g[N][N];int linker[N], lx[N], ly[N];int slack[N];bool visx[N], visy[N];bool dfs(int x){visx[x] = true;for (int y = 0; y < ny; y++){if (visy[y]) continue;int tmp = lx[x] + ly[y] – g[x][y];if (tmp == 0){visy[y] = true;if (linker[y] == -1 || dfs(linker[y])){linker[y] = x;return true;}}else if (slack[y] > tmp)slack[y] = tmp;}return false;}int KM(){memset(linker,-1,sizeof(linker));memset(ly,0,sizeof(ly));for (int i = 0; i < nx; i++){lx[i] = -INF;for (int j = 0; j < ny; j++){if (g[i][j] > lx[i])lx[i] = g[i][j];}}for (int x = 0; x < nx; x++){for (int i = 0; i < ny; i++)slack[i] = INF;while (true){memset(visx, false, sizeof(visx));memset(visy, false, sizeof(visy));if (dfs(x)) break;int d = INF;for (int i = 0; i < ny; i++)if (!visy[i] && d > slack[i])d = slack[i];for (int i = 0; i < nx; i++)if (visx[i])lx[i] -= d;for (int i = 0; i < ny; i++){if (visy[i]) ly[i] += d;else slack[i] -= d;}}}int res = 0;for (int i = 0; i < ny; i++){if (linker[i] != -1)res += g[linker[i]][i];}return res;}int main(){int n;while (scanf(“%d”, &n) != EOF){for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)scanf(“%d”,&g[i][j]);nx = ny = n;printf(“%d\n”,KM());}return 0;}
每个人在他的人生发轫之初，总有一段时光，
