二分图题目泛做（为了对应陈学姐的课件）

题1：BZOJ1854 SCOI2010游戏（最大匹配，如果不能匹配就break）

每个属性x,y分别向i连条边，匹配属性到不能匹配为止。注意是属性找武器，所以要循环属性。

输出即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 const int N = 1000000 + 5;
10 
11 int tim = 0, n, tot = 0;
12 int first[N], next[N<<1];
13 int u[N<<1], v[N<<1];
14 int used[N], girl[N];
15 
16 void Add(int s, int t){
17   ++ tot;
18   u[tot] = s; v[tot] = t;
19   next[tot] = first[u[tot]];
20   first[u[tot]] = tot;
21 }
22 
23 bool find(int now){
24   for(int i = first[now]; i; i = next[i]){
25     if(used[v[i]] != tim){
26       used[v[i]] = tim;
27 
28       if(girl[v[i]] == 0 || find(girl[v[i]])){
29         girl[v[i]] = now;
30         return true;
31       }
32     }
33   }
34 
35   return false;
36 }
37 
38 #define ONLINE_JUDGE
39 int main(){
40 #ifndef ONLINE_JUDGE
41   freopen("game.in", "r", stdin);
42   freopen("game.out", "w", stdout);
43 #endif
44   
45   int x, y;
46   
47   scanf("%d", &n);
48   for(int i = 1; i <= n; ++ i){
49     scanf("%d%d", &x, &y);
50     Add(x, i); Add(y, i);
51   }
52 
53   int ans = 0;
54   for(int i = 1; i <= 10000; ++ i){
55     ++ tim;
56     if(find(i))
57       ++ ans;
58     else break;
59   }
60 
61   printf("%d
", ans);
62 
63 #ifndef ONLINE_JUDGE
64   fclose(stdin); fclose(stdout);
65 #endif
66   return 0;
67 }

BZOJ 1854

题2：HDU2768 Cat V.S. Dog

交了10遍。后来才发现错的地方是因为保存的地方，我是直接return (int)x + (int)ss[0], 但是这样的话，我们要注意C2和D1就是等价的了。。。。做的时候要考虑，我们是把有冲突的人之间连边，不要老考虑狗和猫的关系。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int N = 500 + 5;
 6 const int M = 500 * 500 + 5;
 7 
 8 int tim = 0, tot = 0;
 9 int x = 0, a;
10 int n, m, k;
11 char ss[10];
12 int first[N], nxt[M];
13 int u[M], v[M];
14 int usd[N], girl[N];
15 
16 struct data{
17   string s1, s2;
18 }p[N];
19 
20 void Add(int s, int t){
21   ++ tot;
22   u[tot] = s; v[tot] = t;
23   nxt[tot] = first[u[tot]];
24   first[u[tot]] = tot;
25 }
26 
27 bool find(int x){
28   for(int i = first[x]; i; i = nxt[i]){
29     if(usd[v[i]] != tim){
30       usd[v[i]] = tim;
31       if(!girl[v[i]] || find(girl[v[i]])){
32         girl[v[i]] = x;
33         return true;
34       }
35     }
36   }
37 
38   return false;
39 }
40 
41 void Solve(){
42   memset(first, 0, sizeof first);
43   memset(girl, 0, sizeof girl);
44   tot = 0;
45   
46   cin >> n >> m >> k;
47   for(int i = 1; i <= k; ++ i){
48     cin >> p[i].s1 >> p[i].s2;
49   }
50   for(int i = 1; i <= k; ++ i){
51     for(int j = 1; j <= k; ++ j){
52       if(i != j){
53         if(p[i].s1 == p[j].s2 || p[j].s1 == p[i].s2){
54           Add(i, j); Add(j, i);
55         }
56       }
57     }
58   }
59 
60   int ans = 0;
61   
62   for(int i = 1; i <= k; ++ i){
63     ++ tim;
64     if(find(i))
65       ++ ans;
66   }
67 
68   printf("%d
", k - ans/2);
69 }
70 
71 int main(){
72   ios::sync_with_stdio(false);
73   
74   int t;
75 
76   cin >> t;
77   
78   while(t --){
79     Solve();
80   }
81 
82   return 0;
83 }

HDU 2768

题3： POJ 1325 Machine Schedule

求二分图的最小覆盖：寻找一个最小的点集，使得图中每一条边至少有一个点在该点集中。

二分图的最小覆盖 = 最大匹配。注意所有机器开始都在0模式，所以一开始与0相连的边不要加入二分图。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 const int N = 1000 + 5;
 9 
10 int n, m, k;
11 int first[N], next[N<<1];
12 int u[N<<1], v[N<<1];
13 int usd[N], g[N], tim = 0, tot = 0;
14 
15 void Add(int s, int t){
16   ++ tot;
17   u[tot] = s; v[tot] = t;
18   next[tot] = first[u[tot]];
19   first[u[tot]] = tot;
20 }
21 
22 bool find(int x){
23   for(int i = first[x]; i; i = next[i]){
24     if(usd[v[i]] != tim){
25       usd[v[i]] = tim;
26       if(!g[v[i]] || find(g[v[i]])){
27         g[v[i]] = x;
28         return true;
29       }
30     }
31   }
32 
33   return false;
34 }
35 
36 
37 int main(){
38   int x, y, z;
39   
40   while(scanf("%d", &n)){
41     if(n == 0) break;
42     scanf("%d%d", &m, &k);
43     tot = 0;
44     memset(first, 0, sizeof first);
45     memset(g, 0, sizeof g);
46     
47     for(int i = 1; i <= k; ++ i){
48       scanf("%d%d%d", &x, &y, &z);
49 
50       if(y && z) Add(y, z);
51     }
52 
53     int ans = 0;
54     
55     for(int i = 1; i < n; ++ i){
56       ++ tim;
57       if(find(i)) ++ ans;
58     }
59 
60     printf("%d
", ans);
61   }
62 
63   return 0;
64 }

POJ 1325

题4： POJ 2226 Muddy Fields （感觉这题比较好）

给一个N*M的矩形，*代表泥地，“.”代表草地，求最少用多少块木板可以覆盖泥地。注：不能覆盖草地。

先来考虑可以覆盖草地的情况，那么就是找到每一个*，假设其坐标为i行j列，那么就i->j连边。跑最大匹配。

如果不可以，就把在同一行上的连通的看做一行，同一列上的连通的看做一列。像上面一样连边。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 const int N = 50 + 5;
10 const int NS = 10000 + 5;
11 
12 int r, c;
13 int cnth = 0, cntl = 0;
14 int h[N][N], l[N][N];
15 int lk[N*N][N*N];
16 char str[N][N];
17 int tot = 0, tim = 0, ans = 0;
18 int first[NS], next[NS<<1];
19 int v[NS<<1];
20 int usd[NS], g[NS];
21 
22 void Add(int s, int t){
23   ++ tot;
24   v[tot] = t;
25   next[tot] = first[s];
26   first[s] = tot;
27 }
28 
29 bool find(int x){
30   for(int i = first[x]; i; i = next[i]){
31     if(usd[v[i]] != tim){
32       usd[v[i]] = tim;
33       if(!g[v[i]] || find(g[v[i]])){
34         g[v[i]] = x;
35         return true;
36       }
37     }
38   }
39   return false;
40 }
41 
42 int main(){
43   while(scanf("%d%d", &r, &c) != EOF){
44     for(int i = 1; i <= r; ++ i){
45       scanf("%s", str[i] + 1);
46     }
47 
48     for(int i = 1; i <= r; ++ i){
49       for(int j = 1; j <= c; ++ j){
50         if(str[i][j] == '.') continue;
51         if(h[i][j]) continue;
52         else h[i][j] = ++ cnth;
53         for(int k = j + 1; k <= c; ++ k)
54           if(str[i][k] == '*') h[i][k] = cnth;
55           else break;
56       }
57     }
58     for(int j = 1; j <= c; ++ j){
59       for(int i = 1; i <= r; ++ i){
60         if(str[i][j] == '.') continue;
61         if(l[i][j]) continue;
62         else l[i][j] = ++ cntl;
63         for(int k = i + 1; i <= r; ++ k)
64           if(str[k][j] == '*') l[k][j] = cntl;
65           else break;
66       }
67     }
68 
69     int x, y;
70     
71     for(int i = 1; i <= r; ++ i){
72       for(int j = 1; j <= c; ++ j){
73         if(lk[x = h[i][j]][y = l[i][j]]) continue;
74         lk[x][y] ++;
75         Add(x, y);
76       }
77     }
78     
79     for(int i = 1; i <= cnth; ++ i){
80       ++ tim;
81       if(find(i)) ++ ans;
82     }
83 
84     printf("%d
", ans);
85   }
86 
87   return 0;
88 }

POJ 2226

题5： COJS 骑士共存

求二分图的最大独立集：求一个最大的点集，使任意两点间无直接连边。

二分图的最大独立集 = 点数 - 最大匹配。

把棋盘染色，跑图的时候只跑一半的点。注意常数！注意常数！注意常数！重要的事情说三遍。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int N = 200 + 5;
 6 const int M = 320000 + 5;
 7 
 8 int n, m;
 9 int tot = 0, tim = 0, ans = 0;
10 int first[N * N], next[M<<1];
11 int u[M<<1], v[M<<1];
12 int girl[N * N], usd[N * N];
13 bool b[N * N];
14 int dx[8] = {-2, -1, 1, 2, -2, -1, 1, 2}, dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};                  
15 
16 void Add(int s, int t){
17   ++ tot;
18   u[tot] = s; v[tot] = t;
19   next[tot] = first[s];
20   first[s] = tot;
21 }
22 
23 bool find(int x){
24   for(int i = first[x]; i; i = next[i]){
25     if(usd[v[i]] != tim){
26       usd[v[i]] = tim;
27       if(!girl[v[i]] || find(girl[v[i]])){
28         girl[v[i]] = x;
29         return true;
30       }
31     }
32   }
33   return false;
34 }
35 
36 int c(int i, int j){
37   return j + (i - 1) * n;
38 }
39 
40 int main(){
41 #ifndef ONLINE_JUDGE
42   freopen("knight.in", "r", stdin);
43   freopen("knight.out", "w", stdout);
44 #endif
45   
46   int x, y;
47   
48   scanf("%d%d", &n, &m);
49   for(int i = 1; i <= m; ++ i){
50     scanf("%d%d", &x, &y);
51     b[c(x, y)] = true;
52   }
53 
54   int s, t;
55   
56   for(int i = 1; i <= n; ++ i){
57     for(int j = (i & 1) + 1; j <= n; j += 2){
58       if(!b[s = c(i, j)])
59         for(int k = 0; k < 8; ++ k){
60           if(i + dx[k] < 1 || i + dx[k] > n || j + dy[k] < 1 || j + dy[k] > n) continue;
61           if(b[t = c(i + dx[k], j + dy[k])]) continue;
62           Add(s, t); Add(t, s);
63         }
64     }
65   }
66 
67   for(int i = 1; i <= n; ++ i){
68     for(int j = 1; j <= n; ++ j){
69       if(i + j & 1 && !b[s = c(i, j)]){
70         ++ tim;
71         if(find(s)) ++ ans;
72       }
73     }
74   }
75 
76   printf("%d
", n * n - m - ans);
77 
78 #ifndef ONLINE_JUDGE
79   fclose(stdin); fclose(stdout);
80 #endif
81   return 0;
82 }

COJS 骑士共存

题6： POJ 1422 Air Raid

求二分图的最小路径覆盖，用尽量少的不相交的路径覆盖有向无环图的所有点。

原图的路径覆盖和新图的匹配间有对应关系：每条覆盖边都是匹配中的一条边，且只有路径的最后一个点没有被匹配上路径要求不能相交，恰好对应匹配中两匹配边不能有公共端点于是求最大匹配后，不能被匹配上的点，即是路径的最后一个点。有多少个不能被匹配上的点，就有多少条路径存在路径数=原点数-匹配边数。因此是匹配边数最大，即是使路径数最小

这题是裸题。拆点后直接做。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 const int N = 1000 + 5;
 9 
10 int n, m, k;
11 int first[N], next[N<<1];
12 int u[N<<1], v[N<<1];
13 int usd[N], g[N], tim = 0, tot = 0;
14 
15 void Add(int s, int t){
16   ++ tot;
17   u[tot] = s; v[tot] = t;
18   next[tot] = first[u[tot]];
19   first[u[tot]] = tot;
20 }
21 
22 bool find(int x){
23   for(int i = first[x]; i; i = next[i]){
24     if(usd[v[i]] != tim){
25       usd[v[i]] = tim;
26       if(!g[v[i]] || find(g[v[i]])){
27         g[v[i]] = x;
28         return true;
29       }
30     }
31   }
32 
33   return false;
34 }
35 
36 
37 int main(){
38   int t, x, y;
39 
40   scanf("%d", &t);
41 
42   while(t --){
43     memset(first, 0, sizeof first);
44     memset(g, 0, sizeof g);
45     tot = 0;
46     
47     scanf("%d%d", &n, &m);
48     for(int i = 1; i <= m; ++ i){
49       scanf("%d%d", &x, &y);
50       Add(x, y + n);
51     }
52 
53     int ans = 0;
54     
55     for(int i = 1; i <= n * 2; ++ i){
56       ++ tim;
57       if(find(i)) ++ ans;
58     }
59 
60     printf("%d
", n - ans);
61   }
62 
63   return 0;
64 }

POJ 1422

题7： COJS 魔术球问题（感觉挺好的一个题）

求二分图的最小路径覆盖。

二分把这个题转化成了判定问题。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 60 + 5;
  6 const int M = 320000 + 5;
  7 
  8 int n, tim = 0, tot = 0, ans;
  9 int first[M<<1], next[M<<1], v[M<<1];
 10 int g[M<<1], usd[M<<1];
 11 
 12 void Add(int from, int to){
 13   ++ tot;
 14   v[tot] = to;
 15   next[tot] = first[from];
 16   first[from] = tot;
 17 }
 18 
 19 bool judge(int i, int j){
 20   int tp1, tp2;
 21 
 22   tp1 = i + j; tp2 = sqrt(tp1);
 23   if(tp2 * tp2 == tp1) return true;
 24   return false;
 25 }
 26 void build(int nv){
 27   tot = 0;
 28   memset(first, 0, sizeof first);
 29   memset(g, 0, sizeof g);
 30   
 31   for(int i = 1; i <= nv; ++ i){
 32     for(int j = i + 1; j <= nv; ++ j){
 33       if(judge(i, j)){
 34         Add(i, j);
 35       }
 36     }
 37   }
 38 }
 39 
 40 bool find(int x){
 41   for(int i = first[x]; i; i = next[i]){
 42     if(usd[v[i]] != tim){
 43       usd[v[i]] = tim;
 44 
 45       if(!g[v[i]] || find(g[v[i]])){
 46         g[v[i]] = x;
 47         return true;
 48       }
 49     }
 50   }
 51 
 52   return false;
 53 }
 54 
 55 bool check(int nv){
 56   int kk = 0;
 57   
 58   for(int i = 1; i <= nv; ++ i){
 59     ++ tim;
 60     if(find(i)) ++ kk;
 61   }
 62 
 63   return (nv - kk) <= n;
 64 }
 65 
 66 void Input(){
 67   scanf("%d", &n);
 68 }
 69 
 70 void Solve(){
 71   int l = 1, r = 1600;
 72   int mid;
 73 
 74   while(l <= r){
 75     mid = l + (r - l) / 2;
 76     build(mid);
 77     if(check(mid)){
 78       l = mid + 1;
 79       ans = mid;
 80     }
 81     else r = mid - 1;
 82   }
 83 }
 84 
 85 void Output(){
 86   printf("%d
", ans);
 87 }
 88 
 89 int main(){
 90 #ifndef ONLINE_JUDGE
 91   freopen("balla.in", "r", stdin);
 92   freopen("balla.out", "w", stdout);
 93 #endif
 94 
 95   Input();
 96   Solve();
 97   Output();
 98 
 99 #ifndef ONLINE_JUDGE
100   fclose(stdin); fclose(stdout);
101 #endif
102 
103   return 0;
104 }

COJS 魔术球

题8： BZOJ 3008 象棋

题目大意：一个棋盘，分别给出K个棋子指定的起始位置和终止位置，求把所有棋子都移动到终止位置的最小步数。注意，同一时刻一个格子里面只能有一个棋子。

求最佳完美匹配。先处理出所有棋子到每一个终止位置的最小步数，以最小步数为边权连边，直接跑KM算法就可以。

因为所有棋子都是相同的，那么在将要在同一个格子里面出现的时候，相当于被另一个棋子替掉了。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <iostream>
  6  
  7 using namespace std;
  8  
  9 const int N = 1000 + 5;
 10 const int oo = 0x3f3f3f3f;
 11  
 12 int n, m, k, a, b;
 13 int cnt = 0;
 14 char mp[N][N];
 15 bool vi[N][N];
 16 int dx[10], dy[10];
 17 int w[N][N], head[N], stx[N], sty[N], edx[N], edy[N];
 18 int dst[N][N];
 19  
 20 struct Edge {
 21   int to, next;
 22 }edges[500000 + 5];
 23  
 24 struct QUEUE {
 25   int x, y;
 26 }que[N * 20];
 27  
 28 struct KM {
 29   int tim;
 30   int lx[N], ly[N], sx[N], by[N], st[N], g[N];
 31  
 32   KM() {
 33     tim = 0;
 34     memset(sx, 0, sizeof sx);
 35     memset(by, 0, sizeof by);
 36   }
 37   void Clear() {
 38     memset(g, 0, sizeof g);
 39     memset(lx, 0x80, sizeof lx);
 40     memset(ly, 0, sizeof ly);
 41   }
 42  
 43   bool find(int u) {
 44     sx[u] = tim;
 45     for(int i = head[u]; i; i = edges[i].next) {
 46       int v = edges[i].to;
 47  
 48       if(by[v] == tim) continue;
 49  
 50       int t = lx[u] + ly[v] - w[u][v];
 51  
 52       if(!t) {
 53         by[v] = tim;
 54         if(!g[v] || find(g[v])) {
 55           g[v] = u;
 56           return true;
 57         }
 58       }
 59       else{
 60         st[v] = min(st[v], t);
 61       }
 62     }
 63     return false;
 64   }
 65  
 66   int km() {
 67     Clear();
 68     for(int i = 1; i <= k; ++ i) {
 69       for(int j = 1; j <= k; ++ j) {
 70         lx[i] = max(w[i][j], lx[i]);
 71       }
 72     }
 73     for(int i = 1; i <= k; ++ i) {
 74       memset(st, 0x3f, sizeof st);
 75       for(;;) {
 76         ++ tim;
 77         if(find(i)) break;
 78  
 79         int d = oo;
 80  
 81         for(int j = 1; j <= k; ++ j)
 82           if(by[j] != tim)
 83             d = min(st[j], d);
 84         for(int j = 1; j <= k; ++ j) {
 85           if(sx[j] == tim) lx[j] -= d;
 86           if(by[j] == tim) ly[j] += d;
 87           else st[j] -= d;
 88         }
 89       }
 90     }
 91      
 92     int res = 0;
 93  
 94     for(int i = 1; i <= k; ++ i)
 95       res += w[g[i]][i];
 96  
 97     return res;
 98   }
 99 }bsyx;
100  
101 void Input() {
102   scanf("%d%d%d%d%d", &n, &m, &k, &a, &b);
103   for(int i = 1; i <= n; ++ i) {
104     scanf("%s", mp[i] + 1);
105   }
106   for(int i = 1; i <= k; ++ i) {
107     scanf("%d%d", &stx[i], &sty[i]);
108   }
109   for(int i = 1; i <= k; ++ i) {
110     scanf("%d%d", &edx[i], &edy[i]);
111   }
112 }
113  
114 void bfs(int st_x, int st_y) {
115   int head, tail;
116  
117   memset(vi, false, sizeof vi);
118   head = tail = 1;
119   que[head].x = st_x; que[head].y = st_y;
120   dst[st_x][st_y] = 0;
121   vi[st_x][st_y] = true;
122    
123   while(head <= tail) {
124     int x = que[head].x, y = que[head].y;
125  
126     for(int i = 1; i <= 8; ++ i) {
127       int nx = dx[i] + x;
128       int ny = dy[i] + y;
129  
130       if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
131       if(mp[nx][ny] == '*') continue;
132       if(vi[nx][ny]) continue;
133       ++ tail;
134       que[tail].x = nx; que[tail].y = ny;
135       dst[nx][ny] = dst[x][y] + 1;
136       vi[nx][ny] = true;
137     }
138  
139     ++ head;
140   }
141 }
142  
143 void insert(int from, int to) {
144   ++ cnt;
145   edges[cnt].to = to;
146   edges[cnt].next = head[from];
147   head[from] = cnt;
148 }
149  
150 void Solve(){
151   dx[1] = dx[2] = a; dx[3] = dx[4] = -a; dx[5] = dx[6] = b; dx[7] = dx[8] = -b;
152   dy[1] = dy[3] = b; dy[2] = dy[4] = -b; dy[5] = dy[7] = a; dy[6] = dy[8] = -a;
153  
154   for(int i = 1; i <= k; ++ i) {
155     bfs(stx[i], sty[i]);
156     for(int j = 1; j <= k; ++ j) {
157       insert(i, j);
158       if(!vi[edx[j]][edy[j]])
159         w[i][j] = -oo;
160       else
161         w[i][j] = -dst[edx[j]][edy[j]];
162     }
163   }
164  
165 }
166  
167 void Output() {
168   printf("%d
", -bsyx.km());
169 }
170  
171 #define ONLINE_JUDGE
172 int main() {
173 #ifndef ONLINE_JUDGE
174   freopen("chess.in", "r", stdin);
175   freopen("chess.out", "w", stdout);
176 #endif
177  
178   Input();
179   Solve();
180   Output();
181  
182 #ifndef ONLINE_JUDGE
183   fclose(stdin); fclose(stdout);
184 #endif
185  
186   return 0;
187 }

BZOJ 3008

题9： BZOJ 1070修车

M个技术人员和N个车，每个人修每个车都有不同的时刻，而且在同一个时间内，一个人只能修一辆车。问所有车都被修完的情况下，最小的平均等待时候是多少。

分析：假设三个车ABC都找第一个人修，我们假设A是第一个修的，那么修完A的时候为Wa，另外两个等待的时候为2*Wa，第二个。如果我们假设第二个修的是A，那么修完A的时候，另一个等待的时间是Wa。如果最后修的是A，那么最后只有修的时间Wa。所以我们对一个人拆点，一个人拆成n个点，第i个车向第j个连j*cost的边。跑KM。注意左边的点和右边的点可能不相等，所以这是一个左右不等的KM。注意写法。

  1 #include <bits/stdc++.h>
  2  
  3 using namespace std;
  4  
  5 const int N = 600;
  6 const int M = 100000 + 5;
  7 const int oo = 0x3f3f3f3f;
  8  
  9 int n, m, cnt = 0;
 10 int nx, ny;
 11 int w[N][N], head[N];
 12  
 13  
 14 struct Edge {
 15   int to, next;
 16 }edges[M];
 17  
 18 struct KM {
 19   int lx[N], ly[N], sx[N], by[N], st[N], g[N];
 20   int tim;
 21  
 22   KM() {
 23     tim = 0;
 24     memset(by, 0, sizeof by);
 25     memset(sx, 0, sizeof sx);
 26   }
 27  
 28   void clear() {
 29     memset(g, 0, sizeof g);
 30     memset(lx, 0x80, sizeof lx);
 31     memset(ly, 0, sizeof ly);
 32   }
 33  
 34   bool find(int u) {
 35     sx[u] = tim;
 36     for(int i = head[u]; i; i = edges[i].next) {
 37       int v = edges[i].to;
 38  
 39       if(by[v] == tim) continue;
 40  
 41       int t = lx[u] + ly[v] - w[u][v];
 42  
 43       if(!t) {
 44         by[v] = tim;
 45         if(!g[v] || find(g[v])) {
 46           g[v] = u;
 47           return true;
 48         }
 49       }
 50       else {
 51         st[v] = min(st[v], t);
 52       }
 53     }
 54     return false;
 55   }
 56  
 57   int km() {
 58     clear();
 59     for(int i = 1; i <= nx; ++ i) {
 60       for(int j = 1; j <= ny; ++ j) {
 61         lx[i] = max(lx[i], w[i][j]);
 62       }
 63     }
 64     for(int i = 1; i <= nx; ++ i) {
 65       memset(st, 0x3f, sizeof st);
 66       for(;;) {
 67         ++ tim;
 68         if(find(i)) break;
 69  
 70         int d = oo;
 71  
 72         for(int j = 1; j <= ny; ++ j) {
 73           if(by[j] != tim) {
 74             d = min(st[j], d);
 75           }
 76         }
 77         for(int j = 1; j <= nx; ++ j) {
 78           if(sx[j] == tim) lx[j] -= d;
 79         }
 80         for(int j = 1; j <= ny; ++ j) {
 81           if(by[j] == tim) ly[j] += d;
 82           else st[j] -= d;
 83         }
 84       }
 85     }
 86  
 87     int res = 0;
 88  
 89     for(int i = 1; i <= ny; ++ i) {
 90       res += w[g[i]][i];
 91     }
 92  
 93     return res;
 94   }
 95 }bsyx;
 96  
 97 void insert(int from, int to) {
 98   ++ cnt;
 99   edges[cnt].to = to;
100   edges[cnt].next = head[from];
101   head[from] = cnt;
102      
103 }
104  
105 void Input() {
106   int cost;
107    
108   scanf("%d%d", &m, &n);
109   nx = n; ny = n * m;
110   for(int i = 1; i <= n; ++ i) {
111     int tmp = 0;
112     for(int j = 1; j <= m; ++ j) {
113       scanf("%d", &cost);
114  
115       for(int k = 1; k <= n; ++ k) {
116         w[i][++ tmp] = -cost * k;
117         insert(i, tmp);
118       }
119     }
120   }
121 }
122  
123 void Output() {
124   printf("%.2lf
", (double) -bsyx.km() / n);
125 }
126  
127 int main() {
128   Input();
129   Output();
130  
131   return 0;
132 }

BZOJ 1070

题10： POJ 3686 The Windy's

和题9一样的。

  1 #include <cmath>
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <algorithm>
  7 
  8 using namespace std;
  9 
 10 
 11 const int N = 2500 + 5;
 12 const int M = 150000 + 5;
 13 const int oo = 0x3f3f3f3f;
 14 
 15 int n, m, cnt = 0, nx, ny;
 16 int tmp[N][N], w[N][N];
 17 int head[N];
 18 
 19 struct Edge {
 20   int to, next;
 21 }edges[M<<1];
 22 
 23 struct KM {
 24   int tim;
 25   int lx[N], ly[N], sx[N], by[N], st[N], g[N];
 26 
 27   KM() {
 28     tim = 0;
 29     memset(sx, 0, sizeof sx);
 30     memset(by, 0, sizeof by);
 31   }
 32 
 33   void clear() {
 34     memset(g, 0, sizeof g);
 35     memset(lx, 0x80, sizeof lx);
 36     memset(ly, 0, sizeof ly);
 37   }
 38 
 39   bool find(int u) {
 40     sx[u] = tim;
 41 
 42     for(int i = head[u]; i; i = edges[i].next) {
 43       int v = edges[i].to;
 44 
 45       if(by[v] == tim) continue;
 46 
 47       int t = lx[u] + ly[v] - w[u][v];
 48 
 49       if(!t) {
 50         by[v] = tim;
 51         if(!g[v] || find(g[v])) {
 52           g[v] = u;
 53           return true;
 54         }
 55       }
 56       else {
 57         st[v] = min(st[v], t);
 58       }
 59     }
 60     return false;
 61   }
 62 
 63   int km() {
 64     clear();
 65     for(int i = 1; i <= nx; ++ i) {
 66       for(int j = 1; j <= ny; ++ j) {
 67         lx[i] = max(lx[i], w[i][j]);
 68       }
 69     }
 70     for(int i = 1; i <= nx; ++ i) {
 71       memset(st, 0x3f, sizeof st);
 72       for(;;) {
 73         ++ tim;
 74         if(find(i)) break;
 75 
 76         int d = oo;
 77 
 78         for(int j = 1; j <= ny; ++ j) {
 79           if(by[j] != tim) {
 80             d = min(st[j], d);
 81           }
 82         }
 83         for(int j = 1; j <= nx; ++ j) {
 84           if(sx[j] == tim) lx[j] -= d;
 85         }
 86         for(int j = 1; j <= ny; ++ j) {
 87           if(by[j] == tim) ly[j] += d;
 88           else st[j] -= d;
 89         }
 90       }
 91     }
 92 
 93     int res = 0;
 94 
 95     for(int i = 1; i <= ny; ++ i) {
 96       res += w[g[i]][i];
 97     }
 98 
 99     return res;
100   }
101 }bsyx;
102 
103 void insert(int from, int to) {
104   ++ cnt;
105   edges[cnt].to = to;
106   edges[cnt].next = head[from];
107   head[from] = cnt;
108 }
109 
110 void Input() {
111   scanf("%d%d", &n, &m);
112   nx = n; ny = n * m;
113   for(int i = 1; i <= n; ++ i) {
114     for(int j = 1; j <= m; ++ j) {
115       scanf("%d", &tmp[i][j]);
116     }
117   }
118 }
119 
120 void Solve() {
121   cnt = 0;
122   memset(head, 0, sizeof head);
123 
124   for(int i = 1; i <= n; ++ i) {
125     int temp = 0;
126 
127     for(int j = 1; j <= m; ++ j) {
128       for(int k = 1; k <= n; ++ k) {
129         w[i][++ temp] = -tmp[i][j] * k;
130         insert(i, temp);
131       }
132     }
133   }
134 }
135 
136 void Output() {
137   printf("%.6lf
", (double) -bsyx.km() / n);
138 }
139 
140 int main() {
141   int t;
142 
143   scanf("%d", &t);
144 
145   while(t --) {
146     Input();
147     Solve();
148     Output();
149   }
150 
151   return 0;
152 }

POJ 3686

题11： POJ 3565 Ants

平面上N个白点N个黑点，求在最小距离的情况下两两相配的一个方案。

只要证明所以匹配不会出现交叉的情况就好了。这是很容易证明的。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cmath>
  7 
  8 using namespace std;
  9 
 10 const int N = 200 + 5;
 11 const int M = 10000 + 5;
 12 const double oo = 1000000000;
 13 const double eps = 1e-6;
 14 
 15 int n, cnt = 0;
 16 int head[N], ans[N];
 17 double x[N], y[N], w[N][N];
 18 
 19 
 20 struct Edge {
 21   int to, next;
 22 }edges[M];
 23 
 24 struct KM {
 25   int tim;
 26   int sx[N], by[N], g[N];
 27   double lx[N], ly[N], st[N];
 28 
 29   KM() {
 30     tim = 0;
 31     memset(sx, 0, sizeof sx);
 32     memset(by, 0, sizeof by);
 33   }
 34 
 35   void clear() {
 36     memset(g, 0, sizeof g);
 37     for(int i = 0; i <= n; ++ i) lx[i] = -2139062144.00;
 38     memset(ly, 0, sizeof ly);
 39   }
 40 
 41   bool find(int u) {
 42     sx[u] = tim;
 43     for(int i = head[u]; i; i = edges[i].next) {
 44       int v = edges[i].to;
 45 
 46       if(by[v] == tim) continue;
 47 
 48       double t = lx[u] + ly[v] - w[u][v];
 49 
 50       if(fabs(t) < eps) {
 51         by[v] = tim;
 52         if(!g[v] || find(g[v])) {
 53           g[v] = u;
 54           return true;
 55         }
 56       }
 57       else {
 58         st[v] = min(st[v], t);
 59       }
 60     }
 61     return false;
 62   }
 63 
 64   void km() {
 65     clear();
 66     for(int i = 1; i <= n; ++ i) {
 67       for(int j = 1;j <= n; ++ j) {
 68         lx[i] = max(lx[i], w[i][j]);
 69       }
 70     }
 71     for(int i = 1; i <= n; ++ i) {
 72       for(int j = 0; j <= n; ++ j)
 73         st[j] = 1061109567.00;
 74       for(;;) {
 75         ++ tim;
 76         if(find(i)) break;
 77 
 78         double d = 1000000000;
 79 
 80         for(int j = 1; j <= n; ++ j) {
 81           if(by[j] != tim) {
 82             d = min(st[j], d);
 83           }
 84         }
 85         for(int j = 1; j <= n; ++ j) {
 86           if(sx[j] == tim) lx[j] -= d;
 87           if(by[j] == tim) ly[j] += d;
 88           else st[j] -= d;
 89         }
 90       }
 91     }
 92   }
 93 }bsyx;
 94 
 95 double dist(int a, int b) {
 96   return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
 97 }
 98 
 99 void insert(int from, int to) {
100   ++ cnt;
101   edges[cnt].to = to;
102   edges[cnt].next = head[from];
103   head[from] = cnt;    
104 }
105 
106 void Input() {
107   scanf("%d", &n);
108   for(int i = 1; i <= n; ++ i) {
109     scanf("%lf%lf", &x[i], &y[i]);
110   }
111   for(int i = 1; i <= n; ++ i) {
112     scanf("%lf%lf", &x[i + n], &y[i + n]);
113   }
114 }
115 
116 void Solve() {
117   for(int i = 1; i <= n; ++ i) {
118     for(int j = 1; j <= n; ++ j) {
119       insert(i, j);
120       w[i][j] = -dist(i, j + n);
121     }
122   }
123   bsyx.km();
124 }
125 
126 void Output() {
127   for(int i = 1; i <= n; ++ i) {
128     ans[bsyx.g[i]] = i;
129   }
130   for(int i = 1; i <= n; ++ i) {
131     printf("%d
", ans[i]);
132   }
133 }
134 
135 int main() {
136   Input();
137   Solve();
138   Output();
139 
140   return 0;
141 }

POJ 3565

题12： HDU 3488

模板题。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 200 + 5;
  6 const int M = 30000 + 5;
  7 const int oo = 0x7fffffff;
  8 
  9 int n, m;
 10 int head[N], w[N][N];
 11 int cnt = 0;
 12 
 13 struct Edge{
 14   int to, next;
 15 }edges[M];
 16 
 17 struct KM{
 18   int tim;
 19   int lx[N], ly[N], sx[N], by[N], st[N], g[N];
 20 
 21   KM(){
 22     tim = 0;
 23     memset(sx, 0, sizeof sx);
 24     memset(by, 0, sizeof by);
 25   }
 26   
 27   inline void clear(){
 28     memset(g, 0, sizeof g);
 29     memset(lx, 0x80, sizeof lx);
 30     memset(ly, 0, sizeof ly);
 31   }
 32 
 33   inline bool find(int u){
 34     sx[u] = tim;
 35     for(int i = head[u]; i; i = edges[i].next){
 36       int v = edges[i].to;
 37 
 38       if(by[v] == tim) continue;
 39 
 40       int t = lx[u] + ly[v] - w[u][v];
 41 
 42       if(!t){
 43         by[v] = tim;
 44         if(!g[v] || find(g[v])){
 45           g[v] = u;
 46           return true;
 47         }
 48       }
 49       else{
 50         st[v] = min(st[v], t);
 51       }
 52     }
 53 
 54     return false;
 55   }
 56 
 57   inline int km(){
 58     clear();
 59     for(int i = 1; i <= n; ++ i){
 60       for(int j = 1; j <= n; ++ j){
 61         lx[i] = max(lx[i], w[i][j]);
 62       }
 63     }
 64     for(int i = 1; i <= n; ++ i){
 65       memset(st, 0x3f, sizeof st);
 66       for(;;){
 67         ++ tim;
 68         if(find(i)) break;
 69 
 70         int d = oo;
 71         
 72         for(int j = 1; j <= n; ++ j){
 73           if(by[j] != tim)
 74             d = min(d, st[j]);
 75         }
 76         for(int j = 1; j <= n; ++ j){
 77           if(sx[j] == tim) lx[j] -= d;
 78           if(by[j] == tim) ly[j] += d;
 79           else st[j] -= d;
 80         }
 81       }
 82     }
 83 
 84     int res = 0;
 85     
 86     for(int i = 1; i <= n; ++ i){
 87       res += w[g[i]][i];
 88     }
 89 
 90     return res;
 91   }
 92 }bsyx;
 93 
 94 void insert(int from, int to){
 95   ++ cnt;
 96   edges[cnt].to = to;
 97   edges[cnt].next = head[from];
 98   head[from] = cnt;
 99 }
100 
101 void Input(){
102   int x, y, z;
103   
104   cnt = 0;
105   memset(head, 0, sizeof head);
106   memset(w, 0x80, sizeof w);
107   
108   scanf("%d%d", &n, &m);
109   for(int i = 1; i <= m; ++ i){
110     scanf("%d%d%d", &x, &y, &z);
111     insert(x, y);
112     w[x][y] = max(w[x][y], -z);
113   }
114 }
115 
116 void Output(){
117   printf("%d
", -bsyx.km());
118 }
119 
120 int main(){
121   int t;
122 
123   scanf("%d", &t);
124 
125   while(t --){
126     Input();
127     Output();
128   }
129 
130   return 0;
131 }

HDU 3488