luogu P3386 【模板】二分图匹配

二次联通门 : luogu P3386 【模板】二分图匹配

/*

    luogu P3386 【模板】二分图匹配

    最大流

    设置源点，汇点，连到每条边上

    跑一边最大流即可

*/

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#define Max 100008

#define INF 1e7

using namespace std;

inline int min (int a, int b)

{

    return a < b ? a : b;

}

void read (int &now)

{

    now = ;

    char word = getchar ();

    while (word > '' || word < '')

        word = getchar ();

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

}

struct Edge

{

    int from;

    int to;

    int flow;

    int next;

}edge[Max << ];

int deep[Max];

int Edge_Count;

int edge_list[Max];

int S, T;

inline void AddEdge (int from, int to, int dis)

{

    Edge_Count++;

    edge[Edge_Count].to = to;

    edge[Edge_Count].flow = dis;

    edge[Edge_Count].next = edge_list[from];

    edge_list[from] = Edge_Count;

}

int Get_Flow (int now, int flow)

{

    if (now == T || flow <= )

        return flow;

    int res = , pos;

    for (int i = edge_list[now]; i; i = edge[i].next)

    {

        if (deep[edge[i].to] != deep[now] +  || edge[i].flow <= )

            continue;

        pos = Get_Flow (edge[i].to, min (edge[i].flow, flow));

        edge[i].flow -= pos;

        edge[i ^ ].flow += pos;

        res += pos;

        flow -= pos;

        if (flow <= )

            return res;

    }

    return res;

}

int E, N, M;

int Answer;

void Bfs ()

{

    while (true)

    {

        bool flag = false;

        memset (deep, -, sizeof deep);

        queue <int> Queue;

        Queue.push (S);

        deep[S] = ;

        int now;

        while (!Queue.empty ())

        {

            now = Queue.front ();

            Queue.pop ();

            for (int i = edge_list[now]; i; i = edge[i].next)

                if (deep[edge[i].to] <  && edge[i].flow)

                {

                    deep[edge[i].to] = deep[now] + ;

                    if (edge[i].to == T)

                    {

                        flag = true;

                        break;

                    }

                    Queue.push (edge[i].to);

                }

            if (flag)

                break;

        }

        if (deep[T] <= )

            break;

        Answer += Get_Flow (S, INF);

    }

}

int main (int argc, char *argv[])

{

    read (N);

    read (M);

    read (E);

    S = Max - ;

    T = Max - ;

    int x, y;

    for (int i = ; i <= E; i++)

    {

        read (x);

        read (y);

        if (x > M || y > M)

            continue;

        AddEdge (x, N + y + , );

        AddEdge (N + y + , x, );

    }

    for (int i = ; i <= N; i++)

    {

        AddEdge (S, i, );

        AddEdge (i, S, );

    }

    for (int i = ; i <= M; i++)

    {

        AddEdge (N + i + , T, );

        AddEdge (T, N + i + , );

    }

    Bfs ();

    printf ("%d", Answer);

    return ;

}