二分图

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// eft
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4+100;

int n, m, t, res;
int vis[N], mch[N];

struct Edge {int frm, to, nxt;}e[N<<3]; int cnt, h[N<<3]; 

inline void add_edge (int u, int v) {
   e[++cnt].nxt = h[u], h[u] = cnt;
   e[cnt].frm = u, e[cnt].to = v;
}

inline int dfs (int x) {
   for (int i = h[x]; i; i = e[i].nxt) {
      int y = e[i].to;
      if (vis[y]) continue;
      vis[y] = 1;
      if (!mch[y] || dfs (mch[y])) {
         mch[y] = x;
	 return 1;
      }
   }
   return 0;
}

main () {
   cin >> n >> m >> t;
   for (int i = 1, u, v; i <= t; ++ i) {
      scanf ("%d%d", &u, &v);
      if (u > n || v > m) continue;
      add_edge (u, v);
   }
   for (int i = 1; i <= n; ++ i) {
      memset (vis, 0, sizeof vis);
      if (dfs (i)) ++ res;
   }
   cout << res;
   return 0;
}

PS:

1."if" must special judgement

2.the important thought is:

first.use the U to match V

second. if the V has matched w

third. dfs(w) if we get true,thus the U --> V; else we need to find the other edge of the U