[网络流24题] 飞行员配对方案问题

题意

题解

二分图匹配裸题
不过既然是在网络流24题里面..还是不用匈牙利解了吧
建图 设超级源点s，超级汇点t
对于每个外籍飞行员i，连一条s-i流量为1的边
对于每个英国飞行员j，连一条j-t流量为1的边
对与每个给定的配对方案，连一条i-j流量为1的边
直接跑dinic即可，得到最大流就是能派出的飞机个数。

在输出路径时只需要找对于每个外籍飞行员i的边容量是否为0，若为0说明最大流流过了这条边，输出即可。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = (l); i < (r); i++)
using namespace std;

const int maxn = 400 + 10;
const int mod = 1e9 + 7;
int n, m;
int s = 0, t = 400 + 1;

struct Edge
{
    int to, cap;
    int nxt;
} edges[maxn * maxn];
int head[maxn], deep[maxn], tot = 0;
int cur[maxn];

void addedge(int from,int to,int cost)
{
    edges[tot].nxt = head[from];
    edges[tot].to = to;
    edges[tot].cap = cost;
    head[from] = tot;
    tot++;
}

bool bfs(int s,int t)
{
    memset(deep,-1,sizeof(deep));
    for(int i = 0;i <= maxn;++i) cur[i] = head[i];
    deep[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        for(int i = head[v];i != -1;i = edges[i].nxt){
            Edge &e = edges[i];
            if(e.cap > 0 && deep[e.to] == -1){
                deep[e.to] = deep[v]+1;
                que.push(e.to);
            }
        }
    }
    if(deep[t] == -1) return false;
    return true;
}

int dfs(int v,int t,int f){
    if(!f || v == t) return f;
    int flow = 0,d;
    for(int &i = cur[v];i != -1;i = edges[i].nxt){
        Edge &e = edges[i];
        if(e.cap > 0 && deep[e.to] == deep[v]+1){
            d = dfs(e.to,t,min(e.cap,f));
            flow += d;
            f -= d;
            edges[i].cap -= d;
            edges[i^1].cap += d;
            if(!f) break;
        }
    }
    if(!flow) deep[v] = -2;
    return flow;
}

int Dinic(int s,int t)
{
    int res = 0;
    while(bfs(s,t)){
        res += dfs(s,t,inf);
    }
    return res;
}

void init(int n)
{
    tot = 0;
    for (int i = 0; i <= n; ++i)
    {
        head[i] = -1;
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin >> m >> n;
    init(n);
    for (int i = 1; i <= m; ++i)
    {
        addedge(s, i, 1);
        addedge(i, s, 0);
    }
    for (int i = m + 1; i <= n; ++i)
    {
        addedge(i, t, 1);
        addedge(t, i, 0);
    }
    int u, v;
    while (cin >> u >> v)
    {
        if (u == -1 && v == -1)
            break;
        addedge(u, v, 1);
        addedge(v, u, 0);
    }
    int cnt = Dinic(s, t);
    if (!cnt)
    {
        puts("No Solution!");
        return 0;
    }
    printf("%d\n", cnt);
    for (int u = 1; u <= m; ++u)
    {
        for (int j = head[u]; ~j; j = edges[j].nxt)
        {
            int v = edges[j].to;
            if (v != s && u != s && v != t && edges[j].cap == 0 && edges[j ^ 1].cap == 1)
            {
                printf("%d %d\n", u, v);
            }
        }
    }
    return 0;
}