[POJ3041]Asteroids（二分图，最大匹配）

题目链接：http://poj.org/problem?id=3041

题意：N*N中选最少行或者列，可以覆盖所有的点。

最小点覆盖问题，等于最大匹配。

建图：考虑行，选中某一行，那么行上的点对应的列则不需要被选。根据这一条，建图就行。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <cassert>
 8 #include <cstdio>
 9 #include <bitset>
10 #include <vector>
11 #include <deque>
12 #include <queue>
13 #include <stack>
14 #include <ctime>
15 #include <set>
16 #include <map>
17 #include <cmath>
18 using namespace std;
19 
20 typedef pair<int, int> pii;
21 const int maxn = 1050;
22 const int inf = 0x3f3f3f3f;
23 int n, k;
24 int G[maxn][maxn];
25 int nx,ny;
26 int linker[maxn],lx[maxn],ly[maxn];
27 int slack[maxn];
28 bool visx[maxn],visy[maxn];
29 
30 bool dfs(int x) {
31     visx[x] = true;
32     for(int y = 0; y < ny; y++) {
33         if(visy[y])continue;
34         int tmp = lx[x] + ly[y] - G[x][y];
35         if(tmp == 0) {
36             visy[y] = true;
37             if(linker[y] == -1 || dfs(linker[y])) {
38                 linker[y] = x;
39                 return true;
40             }
41         }
42         else if(slack[y] > tmp)
43             slack[y] = tmp;
44     }
45     return false;
46 }
47 
48 int km() {
49     memset(linker,-1,sizeof(linker));
50     memset(ly,0,sizeof(ly));
51     for(int i = 0;i < nx;i++) {
52         lx[i] = -inf;
53         for(int j = 0;j < ny;j++)
54             if(G[i][j] > lx[i])
55                 lx[i] = G[i][j];
56     }
57     for(int x = 0;x < nx;x++) {
58         for(int i = 0;i < ny;i++)
59             slack[i] = inf;
60         while(true) {
61             memset(visx,false,sizeof(visx));
62             memset(visy,false,sizeof(visy));
63             if(dfs(x))break;
64             int d = inf;
65             for(int i = 0;i < ny;i++)
66                 if(!visy[i] && d > slack[i])
67                     d = slack[i];
68             for(int i = 0;i < nx;i++)
69                 if(visx[i])
70                     lx[i] -= d;
71             for(int i = 0;i < ny;i++) {
72                 if(visy[i])ly[i] += d;
73                 else slack[i] -= d;
74             }
75         }
76     }
77     int res = 0;
78     for(int i = 0;i < ny;i++)
79         if(linker[i] != -1)
80             res += G[linker[i]][i];
81     return res;
82 }
83 
84 int main() {
85     // freopen("in", "r", stdin);
86     int x, y;
87     while(~scanf("%d%d",&n,&k)) {
88         memset(G, 0, sizeof(G));
89         for(int i = 1; i <= k; i++) {
90             scanf("%d%d",&x,&y);
91             G[x-1][y-1]++;
92         }
93         nx = n, ny = n;
94         printf("%d
", km());
95     }
96     return 0;
97 }