题意
题解
二分图匹配裸题
不过既然是在网络流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; }