解题思路
考虑如何建模。
既然是网络流，那么肯定要有源点和汇点。而这个题目并没有什么明显的源点和汇点。
想一想，如果一个飞机能够起飞的话，那么必定有一对可以配对的正副驾驶员。也就是说一条曾广路能够上必定有且只有一对配对的管理员。
这里引入一个超级源点和超级汇点。超级源点就和正驾驶相连，流量为$1$。副驾驶员和汇点相连。模型就建好了。
之后就是跑$Dinic$，网络流模板不难，难的是建模QAQ
附上代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxnode =
105, maxedge =
30003, INF =
2147483647;
int n, m, s, t, head[maxnode], cnt =
1, Depth[maxnode], Ans;
struct Edge {
int nxt, v, w;
}ed[maxedge];
inline void addedge(
int u,
int v,
int w) {
ed[++cnt].nxt =
head[u];
ed[cnt].v = v, ed[cnt].w =
w;
head[u] =
cnt;
}
inline bool BFS() {
queue <
int>
Q;
memset(Depth, 0,
sizeof(Depth));
Depth[s] =
1, Q.push(s);
int u;
while (!
Q.empty()) {
u =
Q.front();
Q.pop();
for(
int i=head[u]; i; i=
ed[i].nxt) {
if(Depth[ed[i].v] ==
0 && ed[i].w >
0) {
Depth[ed[i].v] = Depth[u] +
1;
Q.push(ed[i].v);
if(ed[i].v == t)
return true;
}
}
}
return false;
}
inline int Dinic(
int u,
int cap) {
if(u == t)
return cap;
int delta;
for(
int i=head[u]; i; i=
ed[i].nxt) {
if(ed[i].w >
0 && Depth[ed[i].v] == Depth[u] +
1) {
delta =
Dinic(ed[i].v, min(cap, ed[i].w));
if(delta >
0) {
ed[i].w -=
delta;
ed[i^
1].w +=
delta;
return delta;
}
}
}
return 0;
}
int main() {
scanf("%d%d", &n, &
m);
s =
0, t = n+
1;
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);
static int x, y;
while (scanf(
"%d%d", &x, &y) ==
2) addedge(x, y,
1), addedge(y, x,
0);
while (BFS()) Ans +=
Dinic(s, INF);
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9543665.html
相关资源：数据结构—成绩单生成器
