二分图匹配
你以为我要讲匈牙利?不不不,我不会.我是要讲网络流哒!
呃,我直接说怎么搞吧
你把二分图的两边节点搞出来,左边连一个超级源点,容量为 1
右边连一个超级汇点,容量为 1 然后跑从源到汇的最大流
最大流就是最大匹配,至于为什么...这里借用一下大佬的证明:
首先假设,当前流网络有一个最大流,但它对应的不是最大匹配,那么,我们至少还可以向最大匹配中加入一条边,设为(u,v),显然我们还可以增加条增广路径,s->u->v->t。那么就得到一个更大的流,和假设矛盾。所以假设不成立。同理,假设当前有一个最大匹配,其对应的不是最大流,那么至少还存在一条增广路径,假设s->u->v->t。这时就可以增加边(u,v)到最大匹配中,矛盾。
原文:https://blog.****.net/smartxxyx/article/details/9672181
然后...然后就没了啊.
Code:
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
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
" , Dinic () ) ; system ("pause") ; return 0 ;
}