题目大意：给你一个n*m的矩阵，上面有一些格子上有目标，我们可以在格子的外面用枪打目标，一发子弹可以消灭一行或者一列目标，问你最少多少枪能把目标打光，并且输出开枪的位置（转自http://blog.csdn.net/u013761036/article/details/40154095）
显然的最小点覆盖。最开始用网络流做。。。发现整天TLE。。。发现输出方案有点瑕疵。。改了之后还是T。。看了看题。。
100,000条边？？？？？？？？
果断改匈牙利
一遍过。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <map> 9 #include <string> 10 #include <cmath> 11 #define min(a, b) ((a) < (b) ? (a) : (b)) 12 #define max(a, b) ((a) > (b) ? (a) : (b)) 13 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a)) 14 template<class T> 15 inline void swap(T &a, T &b) 16 { 17 T tmp = a;a = b;b = tmp; 18 } 19 inline void read(int &x) 20 { 21 x = 0;char ch = getchar(), c = ch; 22 while(ch < '0' || ch > '9') c = ch, ch = getchar(); 23 while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); 24 if(c == '-') x = -x; 25 } 26 const int INF = 0x3f3f3f3f; 27 const int MAXN = 2000 + 10; 28 const int MAXM = 2000000 + 10; 29 30 int g[MAXN][MAXN], lk1[MAXN], lk2[MAXN], vis[MAXN], tmp1, tmp2, n, m, num; 31 32 int dfs(int u) 33 { 34 for(int v = 1;v <= n;++ v) 35 { 36 if(!g[u][v] || vis[v]) continue; 37 vis[v] = 1; 38 if(lk2[v] == -1 || dfs(lk2[v])) 39 { 40 lk2[v] = u; 41 lk1[u] = v; 42 return 1; 43 } 44 } 45 return 0; 46 } 47 48 int xiongyali() 49 { 50 int ans = 0; 51 memset(lk1, -1, sizeof(lk1)), memset(lk2, -1, sizeof(lk2)); 52 for(int i = 1;i <= n;++ i) 53 { 54 memset(vis, 0, sizeof(vis)); 55 ans += dfs(i); 56 } 57 return ans; 58 } 59 60 int vis1[MAXN], vis2[MAXN]; 61 void ddfs(int u) 62 { 63 vis1[u] = 1; 64 for(int v = 1;v <= n;++ v) 65 { 66 if(lk2[v] == -1 || !g[u][v] || vis2[v] || vis1[lk2[v]]) continue; 67 vis2[v] = 1; 68 if(lk2[v] == -1) continue; 69 ddfs(lk2[v]); 70 } 71 } 72 73 int main() 74 { 75 while(scanf("%d %d %d", &n, &m, &num) != EOF && n && m && num) 76 { 77 memset(g, 0, sizeof(g)), memset(vis1, 0, sizeof(vis1)), memset(vis2, 0, sizeof(vis2)); 78 for(int i = 1;i <= num;++ i) 79 read(tmp1), read(tmp2), g[tmp1][tmp2] = 1; 80 printf("%d ", xiongyali()); 81 for(int i = 1;i <= n;++ i) 82 if(lk1[i] == -1) ddfs(i); 83 for(int i = 1;i <= n;++ i) if(!vis1[i]) printf("r%d ", i); 84 for(int i = 1;i <= m;++ i) if(vis2[i]) printf("c%d ", i); 85 putchar(' '); 86 } 87 return 0; 88 }