1. 云栖社区>
  2. >
  3. 正文

LOJ6000 「网络流 24 题 - 1」 飞行员配对 二分图坠大匹配

作者:用户 来源:互联网 时间:2018-09-06 10:39:06

二分图匹配网络流24题

LOJ6000 「网络流 24 题 - 1」 飞行员配对 二分图坠大匹配 - 摘要: 本文讲的是LOJ6000 「网络流 24 题 - 1」 飞行员配对 二分图坠大匹配, 大家都很强, 可与之共勉 。 题意:   裸的二分图坠大匹配。 题解:   我萌来想想怎么建图呢(初级向)   首先我萌要一个超级原点 S ,和一个超级汇点 T ,对于一条 a→b 的边,我萌直接建一

大家都很强, 可与之共勉 。

题意:
  裸的二分图坠大匹配。

题解:

  我萌来想想怎么建图呢(初级向)
  首先我萌要一个超级原点 S ,和一个超级汇点 T ,对于一条 a→b 的边,我萌直接建一条从 a 到 b 的弧,流量大于 1 ,就好啦(反正坠后只会流出 1 )。
  之后我萌对于二分图左边的点,源点 S 向他萌分别连一条流量为 1 的弧,保证了这个点出去只能有一个点(要专一)。
  之后我萌对于二分图右边的点,汇点 T 向他萌分别连一条流量为 1 的弧,保证了这个点进来只能有一个点(不花心)。

  然后就跑个坠大流。

  挺萌的

# include <bits/stdc++.h>

# define N 1010

class Network  {
private :
    struct edge  {
        int to, w, nxt ;
        edge ( ) {        }
        edge ( int to, int w, int nxt ) : to ( to ), w ( w ), nxt ( nxt ) {        }  
    } g [N << 1] ;

    int head [N], cur [N], ecnt ;
    int S, T , dep [N] ;

    inline int dfs ( int u, int a )  {
        if ( u == T || ! a )  return a ;
        int flow = 0, v, f ;
        for ( int& i = cur [u] ; i ; i = g [i].nxt )  {
            v = g [i].to ;
            if ( dep [v] == dep [u] + 1 )  {
                f = dfs ( v, std :: min ( g [i].w, a - flow ) ) ;
                g [i].w -= f, g [i ^ 1].w += f ;
                flow += f ;
                if ( a == flow )  return a ;
            }
        }
        if ( ! flow )  dep [u] = -1 ;
        return flow ;
    }

    inline bool bfs ( int S, int T )  {
        static std :: queue < int > q ;
        memset ( dep, 0, sizeof ( int ) * ( T + 1 ) ) ;
        dep [S] = 1 ;
        q.push ( S ) ;
        while ( ! q.empty ( ) )  {
            int u = q.front ( ) ;  q.pop ( ) ;
            for ( int i = head [u] ; i ; i = g [i].nxt )  {
                int& v = g [i].to ;
                if ( g [i].w &&  ! dep [v] )  {
                    dep [v] = dep [u] + 1 ;
                    q.push ( v ) ;
                }
            }
        }
        return dep [T] ;
    }
public :
    Network ( )  {    ecnt = 1 ; }

    inline void add_edge ( int u, int v, int w )  {
        g [++ ecnt] = edge ( v, w, head [u] ) ;     head [u] = ecnt ;
        g [++ ecnt] = edge ( u, 0, head [v] ) ;     head [v] = ecnt ;
    }

    inline int dinic ( int S, int T )  {
        this -> S = S, this -> T = T ;
        int rt = 0 ;
        while ( bfs ( S, T ) )    {
            memcpy ( cur, head, sizeof ( int ) * ( T + 1 ) ) ; 
            rt += dfs ( S, 0x3f3f3f3f ) ;
        }
        return rt ;
    }
} Lazer ;

int main ( )  {
    int n, m ;
    scanf ( "%d%d", & n, & m ) ;
    int a, b ;

    const int S = n + 1, T = n + 2 ;

    n -= m ;

    while ( ~ scanf ( "%d%d", & a, & b ) )  {  // a < b ;
        Lazer.add_edge ( a, b, 0x3f3f3f3f ) ;
    }

    for ( int i = 1 ; i <= m ; ++ i )  Lazer.add_edge ( S, i, 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i )  Lazer.add_edge ( i + m, T, 1 ) ;

    printf ( "%d\n", Lazer.dinic ( S, T ) ) ;

    return 0 ;
}

以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索二分图匹配 网络流24题 ,以便于您获取更多的相关知识。