学了匈牙利算法。
匈牙利算法核心是找增广路经。
可以求出二分图的最大匹配数。
感觉还是挺好理解的。
时间复杂度 邻接矩阵：
邻接表：
空间复杂度 邻接矩阵：
邻接表：
看的这个blog，有些恶趣味。（受不了凤姐那张图。。）
——代码
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 6 int n, m, k, cp, cnt; 7 int girl[10010], to[1000001], next[1000001], head[10010]; 8 //girl[i]记录第i个girl所属的boy 9 bool dog[10010]; 10 //dog[i]记录i是否脱单 11 12 inline void add(int x, int y) 13 { 14 to[cnt] = y; 15 next[cnt] = head[x]; 16 head[x] = cnt++; 17 } 18 19 int find_girl(int u) 20 { 21 int i, v; 22 for(i = head[u]; i != -1; i = next[i])//找所有有好感的对象 23 { 24 v = to[i]; 25 if(!dog[v]) 26 //单身(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了) 27 { 28 dog[v] = 1; 29 if(!girl[v] || find_girl(girl[v]))//名花无主或者能腾出个位置来 30 { 31 girl[v] = u; 32 return 1; 33 } 34 } 35 } 36 return 0; 37 } 38 39 int main() 40 { 41 int i, j, x, y; 42 scanf("%d %d %d", &n, &m, &k); 43 memset(head, -1, sizeof(head)); 44 for(i = 1; i <= k; i++) 45 { 46 scanf("%d %d", &x, &y); 47 if(x > n || y > m) continue; 48 add(x, y);//有暧昧关系 49 } 50 for(i = 1; i <= n; i++) 51 { 52 memset(dog, 0, sizeof(dog)); 53 if(find_girl(i)) cp++; 54 } 55 printf("%d", cp); 56 return 0; 57 }
PS:不要在意变量名函数名这些细节。。
但是感觉匈牙利算法好TM慢啊，所以还是学了dinic，用网络流做好了（深搜版isap会超时，日了狗）。
就是再加一个超级源点s连接集合X的点，和一个超级汇点t连接Y的点。
求s到t的最大流就好。
（这个题集合X和集合Y即使数相同也是两个独立的所以得加一个偏移量，还有测试数据表示看不懂了。）
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 5 using namespace std; 6 7 int n, m, cnt, ans, e; 8 int head[100001], to[2000001], val[2000001], next[2000001], dis[100001], cur[100001]; 9 10 void add(int x, int y, int z) 11 { 12 to[cnt] = y; 13 val[cnt] += z; 14 next[cnt] = head[x]; 15 head[x] = cnt++; 16 } 17 18 int dfs(int u, int t, int maxflow) 19 { 20 if(u == t) return maxflow; 21 int i, ret = 0, d, v; 22 for(i = cur[u]; i != -1; i = next[i]) 23 { 24 v = to[i]; 25 if(val[i] && dis[v] == dis[u] + 1) 26 { 27 d = dfs(v, t, min(val[i], maxflow - ret)); 28 ret += d; 29 val[i] -= d; 30 val[i ^ 1] += d; 31 cur[u] = i; 32 if(ret == maxflow) return ret; 33 } 34 } 35 return ret; 36 } 37 38 bool bfs(int s, int t) 39 { 40 queue <int> q; 41 memset(dis, -1, sizeof(dis)); 42 q.push(s); 43 dis[s] = 0; 44 int i, u, v; 45 while(!q.empty()) 46 { 47 u = q.front(); 48 q.pop(); 49 for(i = head[u]; i != -1; i = next[i]) 50 { 51 v = to[i]; 52 if(val[i] && dis[v] == -1) 53 { 54 dis[v] = dis[u] + 1; 55 if(v == t) return 1; 56 q.push(v); 57 } 58 } 59 } 60 return 0; 61 } 62 63 int main() 64 { 65 int i, j, s, t, x, y; 66 scanf("%d %d %d", &n, &m, &e); 67 memset(head, -1, sizeof(head)); 68 s = 0; 69 t = n + m + 2; 70 for(i = 1; i <= n; i++) 71 { 72 add(s, i, 1); 73 add(i, s, 0); 74 } 75 for(i = 1; i <= m; i++) 76 { 77 add(n + i, t, 1); 78 add(t, n + i, 0); 79 } 80 for(i = 1; i <= e; i++) 81 { 82 scanf("%d %d", &x, &y); 83 if(x > n || y > m) continue; 84 add(x, y + n, 1); 85 add(y + n, x, 0); 86 } 87 while(bfs(s, t)) 88 { 89 for(i = 0; i <= n + m + 2; i++) cur[i] = head[i]; 90 ans += dfs(s, t, 1e9); 91 } 92 printf("%d", ans); 93 return 0; 94 }