【洛谷P2756】飞行员配对方案问题

佚名 6年前 (2019-04-25) 随笔 1804人围观抢沙发百度已收录

题目大意：二分图匹配裸题。

题解：用网络流进行处理。
找配对方案的时候，采用遍历二分图左边的每个节点，找到不与源点相连，且正向边权值为 0，反向边权值为 1 的边，输出即可。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
const int maxm=1e4+10;
const int inf=1<<30;

int n,m,s,t,d[maxn],maxflow;
struct node{int nxt,to,w;}e[maxm<<1];
int tot=1,head[maxn];
inline void add_edge(int from,int to,int w){
    e[++tot]=node{head[from],to,w},head[from]=tot;
    e[++tot]=node{head[to],from,0},head[to]=tot;
}
bool bfs(){
    queue<int> q;
    memset(d,0,sizeof(d));
    d[s]=1,q.push(s);
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].w;
            if(w&&!d[v]){
                d[v]=d[u]+1;
                q.push(v);
                if(v==t)return 1;
            }
        }
    }
    return 0;
}
int dinic(int u,int flow){
    if(u==t)return flow;
    int rest=flow;
    for(int i=head[u];i&&rest;i=e[i].nxt){
        int v=e[i].to,w=e[i].w;
        if(w&&d[v]==d[u]+1){
            int k=dinic(v,min(rest,w));
            if(!k)d[v]=0;
            e[i].w-=k,e[i^1].w+=k,rest-=k;
        }
    }
    return flow-rest;
}

void read_and_parse(){
    int x,y;
    scanf("%d%d",&m,&n);
    while(scanf("%d%d",&x,&y)&&x!=-1)add_edge(x,y,1);
    for(int i=1;i<=m;i++)add_edge(0,i,1);
    for(int i=m+1;i<=n;i++)add_edge(i,n+1,1);
    s=0,t=n+1;
}
void solve(){
    while(bfs())while(int now=dinic(s,inf))maxflow+=now;
    if(maxflow==0)return (void)puts("No Solution!");
    printf("%d\n",maxflow);
    for(int u=1;u<=m;u++)
        for(int i=head[u];i;i=e[i].nxt)
            if(e[i].to!=s&&e[i].w==0&&e[i^1].w==1)
                printf("%d %d\n",u,e[i].to);
}
int main(){
    read_and_parse();
    solve();
    return 0;   
}