洛谷 P2756 飞行员配对方案问题（二分图/网络流，最佳匹配方案）

2024-04-04 10:46:17

P2756 飞行员配对方案问题

题目背景

第二次世界大战时期..

题目描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入格式

第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数(m<=n)。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。

接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。最后以 2个-1 结束。

输出格式

第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

输入输出样例

输入 #1复制

输出 #1复制

思路：

二分图最大匹配的裸题，可以用匈牙利直接求解，同时用linker数组输出具体的方案。

或者用最大流求解，

把外籍飞行员化为左边的点

英国飞行员化为右边的点，

即一个左右点之间的最大匹配问题，

然后建立一个超级源点0，将超级源点和所有左边的点相连，流量为1.

建立一个超级汇点n+1，将超级汇点和所有右边的点相连，流量为1.

然后左边和右边的连边即为题目给的可行边，流量也为1.

然后跑最大流，就是最佳匹配方案数。

我是用的ISAP算法跑的网络流。

中间边如果残余流量为0，那么这个边的两个节点就是匹配方案中的一个匹配对。

网络流代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline void getInt(int* p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define N 1000
#define INF 100000000
struct Edge
{
    int from, to, cap, flow;
};

struct ISAP
{
    int n, m, s, t;
    vector<Edge>edges;
    vector<int>G[N];
    bool vis[N];
    int d[N], cur[N];
    int p[N], num[N]; //比Dinic算法多了这两个数组，p数组标记父亲结点，num数组标记距离d[i]存在几个
    void addedge(int from, int to, int cap)
    {
        edges.push_back((Edge) {from, to, cap, 0});
        edges.push_back((Edge) {to, from, 0, 0});
        int m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    int Augumemt()
    {
        int x = t, a = INF;
        while (x != s) //找最小的残量值
        {
            Edge&e = edges[p[x]];
            a = min(a, e.cap - e.flow);
            x = edges[p[x]].from;
        }
        x = t;
        while (x != s) //增广
        {
            edges[p[x]].flow += a;
            edges[p[x] ^ 1].flow -= a;
            x = edges[p[x]].from;
        }
        return a;
    }
    void bfs()//逆向进行bfs
    {
        memset(vis, 0, sizeof(vis));
        queue<int>q;
        q.push(t);
        d[t] = 0;
        vis[t] = 1;
        while (!q.empty())
        {
            int x = q.front(); q.pop();
            int len = G[x].size();
            for (int i = 0; i < len; i++)
            {
                Edge&e = edges[G[x][i]];
                if (!vis[e.from] && e.cap > e.flow)
                {
                    vis[e.from] = 1;
                    d[e.from] = d[x] + 1;
                    q.push(e.from);
                }
            }
        }
    }

    int Maxflow(int s, int t) //根据情况前进或者后退，走到汇点时增广
    {
        this->s = s;
        this->t = t;
        int flow = 0;
        bfs();
        memset(num, 0, sizeof(num));
        for (int i = 0; i < n; i++)
            num[d[i]]++;
        int x = s;
        memset(cur, 0, sizeof(cur));
        while (d[s] < n)
        {
            if (x == t) //走到了汇点，进行增广
            {
                flow += Augumemt();
                x = s; //增广后回到源点
            }
            int ok = 0;
            for (int i = cur[x]; i < G[x].size(); i++)
            {
                Edge&e = edges[G[x][i]];
                if (e.cap > e.flow && d[x] == d[e.to] + 1)
                {
                    ok = 1;
                    p[e.to] = G[x][i]; //记录来的时候走的边，即父边
                    cur[x] = i;
                    x = e.to; //前进
                    break;
                }
            }
            if (!ok) //走不动了，撤退
            {
                int m = n - 1; //如果没有弧，那么m+1就是n，即d[i]=n
                for (int i = 0; i < G[x].size(); i++)
                {
                    Edge&e = edges[G[x][i]];
                    if (e.cap > e.flow)
                        m = min(m, d[e.to]);
                }
                if (--num[d[x]] == 0)break; //如果走不动了，且这个距离值原来只有一个，那么s-t不连通，这就是所谓的“gap优化”
                num[d[x] = m + 1]++;
                cur[x] = 0;
                if (x != s)
                    x = edges[p[x]].from; //退一步，沿着父边返回
            }
        }
        return flow;
    }
};
ISAP gao;
int n, m;

int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    du2(m, n);
    int x, y;
    while (~scanf("%d %d", &x, &y))
    {
        if (x + y == -2)
        {
            break;
        }
        gao.addedge(x, y, 1);
    }
    // gao.s = 0;
    // gao.t = n + 1;
    repd(i, 1, m)
    {
        gao.addedge(0, i, 1);
    }
    repd(i, m + 1, n)
    {
        gao.addedge(i, n + 1, 1);
    }
    gao.n = n + 2;
    printf("%d\n", gao.Maxflow(0, n + 1) );
    repd(i, 1, m)
    {
        for (auto yy : gao.G[i])
        {
            Edge temp =  gao.edges[yy];
            int v = temp.to;
            if (v > m && v <= n && temp.flow == 1)
            {
                printf("%d %d\n", i, v );
            }
        }
    }
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}

匈牙利代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline void getInt(int* p);
const int maxn = 10010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int linker[maxn * 2];
bool used[maxn * 2];
std::vector<int> son[maxn];
bool dfs(int u)
{

    for (auto v : son[u]) {
        if (!used[v]) {
            used[v] = true;
            if (linker[v] == -1 || dfs(linker[v])) {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}

int n, m;
int hungarian()
{
    int res = 0;
    for (int i = 0; i <= n; i++) {
        linker[i] = -1;
    }
    for (int u = 1; u <= m; u++) {
        for (int i = 1; i <= n ; i++)
        {
            used[i] = 0;
        }// 根据题目判断是否改memset
        if (dfs(u))
        {
            res++;
        }
    }
    return res;
}
int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    du2(m, n);
    int x, y;
    while (~scanf("%d %d", &x, &y))
    {
        if (x + y == -2)
        {
            break;
        } else
        {
            son[x].push_back(y);
            son[y].push_back(x);
        }
    }
    cout << hungarian() << endl;
    repd(i, 1, n)
    {
        // chu(linker[i]);
        if (linker[i] != -1)
        {
            printf("%d %d\n", i, linker[i] );
        }
    }
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}

码农公寓