[LuoguP2756] 飞行员配对方案问题

分析

二分图匹配,直接网络流模板

输出方案的时候,判断每条边是否图上剩余容量为 0 的边即可

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=105,M=1e5,INF=0x3f3f3f3f;
int n,m,s,t,max_flow;

struct qxx{int nex,t,v;};
qxx e[M];
int h[N],cnt=1;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
void add_flow(int f,int t,int v){add_path(f,t,v);add_path(t,f,0);}

int rk[N];
bool bfs(){memset(rk,0,sizeof(rk));
    queue<int> q;
    q.push(s),rk[s]=1;
    while(q.size()){int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
            if(w&&!rk[v])rk[v]=rk[u]+1,q.push(v);
        }
    }
    return rk[t];
}
int dinic(int u,int flow){if(u==t)return flow;
    int x,rest=flow;
    for(int i=h[u];i&&rest;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
        if(!w||rk[v]!=rk[u]+1)continue;
        x=dinic(v,min(rest,w));
        if(x)e[i].v-=x,e[i^1].v+=x,rest-=x;
        else rk[v]=0;
    }
    return flow-rest;
}
int main(){scanf("%d%d",&m,&n);
    int x,y;
    while(~scanf("%d%d",&x,&y)&&x!=-1&&y!=-1)add_flow(x,y,1);
    s=0,t=n+1;
    for(int i=1;i<=m;i++)add_flow(s,i,1);
    for(int i=m+1;i<=n;i++)add_flow(i,t,1);
    while(bfs())for(int i=dinic(s,INF);i;i=dinic(s,INF))max_flow+=i;
    if(!max_flow)return puts("No Solution!"),0;
    printf("%d\n",max_flow);
    for(int u=1;u<=m;u++)for(int i=h[u];i;i=e[i].nex)
        if(e[i].v==0&&e[i].t!=s&&e[i].t!=t)printf("%d %d\n",u,e[i].t);
    return 0;
}

 上一篇
卡特兰数 -Catalan 卡特兰数 -Catalan
卡特兰数又称卡塔兰数,英文名 Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁 · 查理 · 卡塔兰 (1814–1894) 的名字来命名。 计算 \begin{split} &T_0=
2018.12.21
下一篇 
[LuoguP3386] 二分图匹配 [LuoguP3386] 二分图匹配
分析网络流算法,左部右部分别连源点汇点,置容量为 1,跑一遍 dinic 或者 EK 即可 代码#include<cstdio> #include<cstring> #include<queue> using namesp
2018.12.21
  目录