题意：n*n的棋盘上有n枚棋子。现在要让你以最小的步数把棋盘分隔开（可以是横竖着的五个一排， 也可以是两个对角线）。问你最小步数
思路：首先枚举各个最终状态起始状态与最终状态建边权值为花费的负数，然后求最大权匹配去一下最大值。最后答案再取相反数。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-25 19:54 5 * Filename : uva_1045.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 101; 34 int nx, ny, Map[LEN][LEN], n; 35 int link[LEN], lx[LEN], ly[LEN], slack[LEN], visx[LEN], visy[LEN]; 36 struct P{int x, y;}p[LEN]; 37 38 //template from kuangbin 39 int dfs(int x){ 40 visx[x] = 1; 41 for(int y=0; y<ny; y++){ 42 if(visy[y]) continue; 43 int tmp = lx[x] + ly[y] - Map[x][y]; 44 if(!tmp){ 45 visy[y] = 1; 46 if(link[y] < 0 || dfs(link[y])){ 47 link[y] = x; 48 return true; 49 } 50 }else if(slack[y] > tmp) slack[y] = tmp; 51 } 52 return false; 53 } 54 55 int KM(){ 56 memset(link, -1, sizeof link); 57 memset(ly, 0, sizeof ly); 58 for(int i=0; i<nx; i++){ 59 lx[i] = -INF; 60 for(int j=0; j<ny; j++) 61 if(Map[i][j] > lx[i]) lx[i] = Map[i][j]; 62 } 63 for(int x=0; x<nx; x++){ 64 for(int i=0; i<ny; i++) slack[i] = INF; 65 while(true){ 66 memset(visx, 0, sizeof visx); 67 memset(visy, 0, sizeof visy); 68 if(dfs(x)) break; 69 int d = INF; 70 for(int i=0; i<ny; i++) 71 if(!visy[i] && d > slack[i]) d = slack[i]; 72 for(int i=0; i<nx; i++) if(visx[i]) lx[i] -= d; 73 for(int i=0; i<ny; i++){ 74 if(visy[i]) ly[i] += d; 75 else slack[i] -= d; 76 } 77 } 78 } 79 int ret = 0; 80 for(int i=0; i<ny; i++) 81 if(link[i] != -1) ret += Map[link[i]][i]; 82 return ret; 83 } 84 85 inline int dis(int a, int b, int c, int d){return abs(a-c) + abs(b-d);} 86 87 int main() 88 { 89 // freopen("in.txt", "r", stdin); 90 91 int kase = 1; 92 while(scanf("%d", &n)!=EOF && n){ 93 nx = ny = n; 94 for(int i=0; i<n; i++){ 95 scanf("%d%d", &p[i].x, &p[i].y); 96 p[i].x--;p[i].y--; 97 } 98 int ans = -INF; 99 //row 100 for(int i=0; i<n; i++){ 101 memset(Map, 0x3f, sizeof Map); 102 for(int j=0; j<n; j++) 103 for(int k=0; k<n; k++){ 104 Map[j][k] = -dis(p[j].x, p[j].y, i, k); 105 } 106 ans = max(ans, KM()); 107 } 108 //col 109 for(int i=0; i<n; i++){ 110 memset(Map, 0x3f, sizeof Map); 111 for(int j=0; j<n; j++) 112 for(int k=0; k<n; k++) 113 Map[j][k] = -dis(p[j].x, p[j].y, k, i); 114 ans = max(ans, KM()); 115 } 116 // 117 memset(Map, 0x3f, sizeof Map); 118 for(int i=0; i<n; i++) 119 for(int j=0; j<n; j++){ 120 Map[i][j] = -dis(p[i].x, p[i].y, j, j); 121 } 122 ans = max(ans, KM()); 123 memset(Map, 0x3f, sizeof Map); 124 for(int i=0; i<n; i++) 125 for(int j=0; j<n; j++) 126 Map[i][j] = -dis(p[i].x, p[i].y, j, n-j-1); 127 ans = max(ans, KM()); 128 ans = -ans; 129 printf("Board %d: %d moves required. ", kase++, ans); 130 } 131 return 0; 132 }