二分图匹配

你以为我要讲匈牙利?不不不,我不会.我是要讲网络流哒!

呃,我直接说怎么搞吧

你把二分图的两边节点搞出来,左边连一个超级源点,容量为 $1$

右边连一个超级汇点,容量为 $1$ 然后跑从源到汇的最大流

最大流就是最大匹配,至于为什么…我不会证明.(反正你是学 $OI$ 的,不需要会证明)

然后…然后就没了啊.

$Code:$

/*
贴一点定理
最大匹配数：最大匹配的匹配边的数目
最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择
最大独立数：选取最多的点，使任意所选两点均不相连
最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。
定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）
定理2：最大匹配数 = 最大独立数
定理3：最小路径覆盖数 = 顶点数 - 最大匹配数
*/
#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\n" , Dinic () ) ; system ("pause") ; return 0 ;
}