【网络流24题-洛谷P2756 飞行员配对方案问题】 stdKonjac的小站

传送门

题目背景

第二次世界大战时期..

题目描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的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：

5 10

1 7

1 8

2 6

2 9

2 10

3 7

3 8

4 7

4 8

5 10

-1 -1

输出样例#1：

1 7

2 9

3 8

5 10

二分图最大匹配问题，建立超级源点和一端集合\(X\)相连，超级汇点与另一端集合\(Y\)相连，然后\(X\)与\(Y\)间按照题目给定图建图，所有的边容量都为1，然后从源点到汇点跑一次最大流，答案就是最大配对数。

至于可行解，在配对的时候记录一下配对的是哪个点就好了。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;
const int maxN = 200;
const int INF = 0x3f3f3f3f;
int m, n;
int ans;
int Source, Sink;

int first[maxN];
int Size;
struct Edge {
    int next;
    int to;
    int flow;
};
Edge e[maxN << 4];

int cur[maxN];
int dis[maxN];
int pre[maxN];
int match[maxN];

void addEdge(int x, int y, int cap) {
    e[Size].next = first[x];
    e[Size].to = y;
    e[Size].flow = cap;
    first[x] = Size++;
    e[Size].next = first[y];
    e[Size].to = x;
    e[Size].flow = 0;
    first[y] = Size++;
}

bool BFS(int Source, int Sink) {
    queue<int> que;
    memset(dis, -1, sizeof(dis));
    dis[Source] = 0;
    que.push(Source);
    while (!que.empty()) {
        int now = que.front();
        que.pop();
        for (int i = first[now]; ~i; i = e[i].next) {
            int next = e[i].to;
            if (dis[next] == -1 && e[i].flow) {
                dis[next] = dis[now] + 1;
                que.push(next);
            }
        }
    }
    return dis[Sink] != -1;
}

int DFS(int now, int Sink, int minFlow) {
    if (now == Sink || !minFlow) {
        return minFlow;
    }
    int flow = 0;
    for (int i = cur[now]; ~i; i = e[i].next) {
        cur[now] = i;
        int next = e[i].to;
        if (dis[next] == dis[now] + 1) {
            int extraFlow = DFS(next, Sink, min(minFlow, e[i].flow));
            if (extraFlow) {
                match[now] = next;  //记录匹配对象
                minFlow -= extraFlow;
                flow += extraFlow;
                e[i].flow -= extraFlow;
                e[i ^ 1].flow += extraFlow;
                if (!minFlow) {
                    break;
                }
            }
        }
    }
    return flow;
}

int Dinic() {
    int maxFlow = 0;
    while (BFS(Source, Sink)) {
        memcpy(cur, first, sizeof(first));
        maxFlow += DFS(Source, Sink, INF);
    }
    return maxFlow;
}
void init() {
    Size = 0;
    memset(first, -1, sizeof(first));
}
int main() {
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
    init();
    scanf("%d %d", &m, &n);
    Source = 0, Sink = n + 1;
    int u, v;
    while (~scanf("%d %d", &u, &v)) {
        if (u == -1 && v == -1) {
            break;
        }
        addEdge(u, v, 1);
    }
    for (int i = 1; i <= m; i++) {
        addEdge(Source, i, 1);
    }
    for (int i = m + 1; i <= n; i++) {
        addEdge(i, Sink, 1);
    }
    ans = Dinic();
    cout << ans << endl;
    if (!ans) {
        cout << "No Solution!" << endl;
    } else {
        for (int i = 1; i <= m; i++) {
            if (match[i]) {
                cout << i << " " << match[i] << endl;
            }
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include <algorithm>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <queue>

#include <stack>

#include <string>

using namespace std;

const int maxN = 200;

const int INF = 0x3f3f3f3f;

int m, n;

int ans;

int Source, Sink;

int first[maxN];

int Size;

struct Edge {

int next;

int to;

int flow;

};

Edge e[maxN << 4];

int cur[maxN];

int dis[maxN];

int pre[maxN];

int match[maxN];

void addEdge(int x, int y, int cap) {

e[Size].next = first[x];

e[Size].to = y;

e[Size].flow = cap;

first[x] = Size++;

e[Size].next = first[y];

e[Size].to = x;

e[Size].flow = 0;

first[y] = Size++;

}

bool BFS(int Source, int Sink) {

queue<int> que;

memset(dis, -1, sizeof(dis));

dis[Source] = 0;

que.push(Source);

while (!que.empty()) {

int now = que.front();

que.pop();

for (int i = first[now]; ~i; i = e[i].next) {

int next = e[i].to;

if (dis[next] == -1 && e[i].flow) {

dis[next] = dis[now] + 1;

que.push(next);

}

return dis[Sink] != -1;

}

int DFS(int now, int Sink, int minFlow) {

if (now == Sink || !minFlow) {

return minFlow;

}

int flow = 0;

for (int i = cur[now]; ~i; i = e[i].next) {

cur[now] = i;

int next = e[i].to;

if (dis[next] == dis[now] + 1) {

int extraFlow = DFS(next, Sink, min(minFlow, e[i].flow));

if (extraFlow) {

match[now] = next; //记录匹配对象

minFlow -= extraFlow;

flow += extraFlow;

e[i].flow -= extraFlow;

e[i ^ 1].flow += extraFlow;

if (!minFlow) {

break;

}

return flow;

}

int Dinic() {

int maxFlow = 0;

while (BFS(Source, Sink)) {

memcpy(cur, first, sizeof(first));

maxFlow += DFS(Source, Sink, INF);

}

return maxFlow;

}

void init() {

Size = 0;

memset(first, -1, sizeof(first));

}

int main() {

freopen("test.in", "r", stdin);

freopen("test.out", "w", stdout);

init();

scanf("%d %d", &m, &n);

Source = 0, Sink = n + 1;

int u, v;

while (~scanf("%d %d", &u, &v)) {

if (u == -1 && v == -1) {

break;

}

addEdge(u, v, 1);

}

for (int i = 1; i <= m; i++) {

addEdge(Source, i, 1);

}

for (int i = m + 1; i <= n; i++) {

addEdge(i, Sink, 1);

}

ans = Dinic();

cout << ans << endl;

if (!ans) {

cout << "No Solution!" << endl;

} else {

for (int i = 1; i <= m; i++) {

if (match[i]) {

cout << i << " " << match[i] << endl;

}

return 0;

}