二分图匹配模板

洛谷【P3386】

题目背景

二分图

感谢@一扶苏一提供的hack数据

题目描述

给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数

输入输出格式

输入格式：

第一行，n,m,e

第二至e+1行，每行两个正整数u,v，表示u,v有一条连边

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1：复制

1 1 1
1 1

输出样例#1：复制

说明

因为数据有坑，可能会遇到

算法：二分图匹配

本来应该是一个匈牙利算法的板子但是我不想写匈牙利而且所有的二分图匹配都能用网络流解决，那么不如跑一遍dinic，而且更省时间。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 99999999
const int maxn=1e6+5;
struct Edge
{
    int from, to;
    int flow;       //流量
    Edge(int u, int v, int f): from(u), to(v), flow(f) {}
};
int n, m;
int s, t;
vector<Edge> edges;//边数的两倍
vector<int> G[maxn];//G[i][j]表示节点i的第j条边在edges数组中的序号
int dis[maxn];//从起点s到i的距离
int cur[maxn];//当前弧下标

void init(int n)
{
    for(int i=0; i<n; i++) G[i].clear();
    edges.clear();
}

void add_edge(int from, int to, int flow)
{
    edges.push_back(Edge(from,to,flow));
    edges.push_back(Edge(to,from,0));
    int sz = edges.size();
    G[from].push_back(sz-2);
    G[to].push_back(sz-1);
}

bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i=0; i<G[u].size(); i++)
        {
            Edge &e = edges[G[u][i]];
            if(dis[e.to]==-1 && e.flow>0)  //有余量且没有分过层
            {
                dis[e.to] = dis[u]+1;
                q.push(e.to);
            }
        }
    }
    if(dis[t]==-1)      //如果汇点没有被分层过说明到不了汇点
        return false;
    return true;
}

int dfs(int x, int a) //当前节点x，源点出发余量最小的弧的剩余容量a，函数返回本次增广的流量,返回0表示无法增广
{
    if(x==t) return a;  //如果走到了汇点，返回此时余量，即增广的流量
    int f;
    for(int &i=cur[x]; i<G[x].size(); i++)  //i 加上引用，进行当前弧优化，避免对没有用的路径进行多次检查
    {
        Edge &e = edges[G[x][i]];            //下面if的前两句是说，图依然联通且到达了下一层
        if(dis[x]+1==dis[e.to] && e.flow>0 && (f=dfs(e.to,min(a, e.flow)))>0)     //dfs就是求增广路，即f>0可以到汇点
        {
            e.flow -= f;                  //正向流量减少
            edges[G[x][i]^1].flow += f;   //逆向流量增加
            return f;                    //返回本次增广的流量
        }
    }
    return 0;
}

int dinic(int s, int t)
{
    int ans=0;
    while(bfs())
    {
        memset(cur,0,sizeof(cur));
        int f;
        while(f = dfs(s,INF)) ans += f;   //一次bfs可以进行多次增广
    }
    return ans;
}

int main()
{
    int k;
    scanf("%d %d %d",&n,&m,&k);
    {
        int x,y,flow;
        init(n+m+5);
        s=0,t=n+m+1;
        for(int i=1; i<=n; i++)
            add_edge(s,i,1);
        for(int i=1; i<=k; i++)
        {
            scanf("%d %d",&x,&y);
            if(y>m) continue;
            if(x>n) continue;
            add_edge(x,y+n,1);
        }
        for(int i=1; i<=m; i++)
            add_edge(i+n,t,1);
        int ans=dinic(s,t);
        printf("%d
",ans);
    }
    return 0;
}

View Code

附匈牙利的板子

using namespace std;
bool f[1001][1001],vis[1001];
int n,m,e,ans,mat[1001]; 
bool dfs(int x){
    for(int i=1;i<=m;i++){
        if(f[x][i] and !vis[i]){
            vis[i]=1;
            if(!mat[i]){
                mat[i]=x;
                return 1;
            }else{
                if(dfs(mat[i])){
                    mat[i]=x;
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x<=n and y<=m)f[x][y]=1;
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }
    printf("%d
",ans);
    return 0;
}

View Code