你以为我要讲匈牙利?不不不,我不会.我是要讲网络流哒!
呃,我直接说怎么搞吧
你把二分图的两边节点搞出来,左边连一个超级源点,容量为 1
右边连一个超级汇点,容量为 1 然后跑从源到汇的最大流
最大流就是最大匹配,至于为什么...这里借用一下大佬的证明:
首先假设，当前流网络有一个最大流，但它对应的不是最大匹配，那么，我们至少还可以向最大匹配中加入一条边，设为（u，v），显然我们还可以增加条增广路径，s->u->v->t。那么就得到一个更大的流，和假设矛盾。所以假设不成立。同理，假设当前有一个最大匹配，其对应的不是最大流，那么至少还存在一条增广路径，假设s->u->v->t。这时就可以增加边（u，v）到最大匹配中，矛盾。原文：https://blog.csdn.net/smartxxyx/article/details/9672181
然后...然后就没了啊.
Code:
#include#include #include #include #include const int N = 1e3 + 5 ;const int INF = 1061109567 ;using std::queue ;struct edge { int to , next , flow ;} e[(N*N<<2)] ;int n , m , tot = 1 , head[N+N] , flor[N+N] , s , t , eg ;inline void build (int u , int v , int w) { e[++tot].next = head[u] ; e[tot].to = v ; e[tot].flow = w ; head[u] = tot ; return;}queue < int > q ;inline bool bfs ( int cur ) { while ( ! q.empty () ) q.pop () ; memset ( flor , false , sizeof ( flor ) ) ; flor[cur] = 1 ; q.push ( cur ) ; while ( ! q.empty () ) { int j = q.front () ; q.pop () ; for (int i = head[j] ; i ; i = e[i].next) { int k = e[i].to ; if ( ! flor[k] && e[i].flow ) { flor[k] = flor[j] + 1 ; q.push ( k ) ; } } } return flor[t] ;}inline int dfs ( int cur , int dist ) { if ( cur == t ) return dist ; for (int i = head[cur] ; i ; i = e[i].next) { int k = e[i].to ; if ( flor[k] == flor[cur] + 1 && e[i].flow ) { int now = dfs ( k , std::min ( e[i].flow , dist ) ); if ( now != 0 ) { e[i].flow -= now ; e[i^1].flow += now ; return now ; } } } return 0 ;}inline int Dinic () { int ans = 0 ; while ( bfs ( s ) ) while ( int now = dfs ( s , INF ) ) ans += now ; return ans ;}int main () { scanf ("%d%d%d" , & n , & m , & eg ) ; s = 0 ; t = n + m + 1 ; for (int i = 1 ; i <= n ; ++ i) build ( s , i , 1 ) , build ( i , s , 0 ) ; for (int i = n + 1 ; i <= n + m ; ++ i) build ( t , i , 0 ) , build ( i , t , 1 ) ; while ( eg -- ) { register int u , v ; scanf ("%d%d" , & u , & v ) ; if ( u > n || v > m ) continue ; build ( u , v + n , 1 ) ; build ( v + n , u , 0 ) ; } printf ("%d\n" , Dinic () ) ; system ("pause") ; return 0 ;}