题目大意
有 $\text{N1}$ 本书 $\text{N2}$本练习册 $\text{N3}$本答案，一本书只能和一本练习册和一本答案配对。给你一些书和练习册，书和答案的可能的配对关系。问你最多可以配成多少套完整的书册。
解题思路
我已开始直接建立超级源点汇点，然后源点$\rightarrow $练习册连边，练习册$\rightarrow $书连边，书$\rightarrow $答案连边，答案$\rightarrow $汇点连边。然后直接跑 $\text{Dinic}$。$\text{RE}$ 了之后 $\text{TLE}$ 了。后来发现如果「 书 」这个环节不进行拆点的话，会有部分练习册和答案共用一本书。这样就错了。又加了拆点的过程。还是 $\text{TLE}$。又发现是我的$\text{Dinic}$ 写的太丑，每次增广只能增广 $1$ 。简直了，又去题解，里找了个写的好看的 $\text{Dinic}$ 重新搞了一线板子，这才过了这道题。
附上代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 8e6+
3, INF =
2147483647;
int n1, n2, n3, s, t, m, head[maxn], cnt =
1, Depth[maxn], Ans;
struct edge {
int v, w, nxt;
}ed[maxn];
inline int read() {
int x =
0, f =
1;
char c =
getchar();
while (c <
'0' || c >
'9') {
if(c ==
'-') f = -
1; c =
getchar();}
while (c <=
'9' && c >=
'0') {x = x*
10 + c-
'0'; c =
getchar();}
return x *
f;
}
inline void addedge (
int x,
int y,
int z) {
ed[++cnt].nxt =
head[x];
ed[cnt].v = y, ed[cnt].w =
z;
head[x] =
cnt;
}
inline bool bfs() {
queue<
int>
Q;
memset(Depth, 0,
sizeof(Depth));
Q.push(s), Depth[s] =
1;
int u;
while (!
Q.empty()) {
u =
Q.front();
Q.pop();
for(
int i=head[u]; i; i=
ed[i].nxt) {
if(ed[i].w >
0 && !
Depth[ed[i].v]) {
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 || !cap)
return cap;
int delta, ret =
0;
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(ed[i].w, cap-
ret));
if(delta >
0) {
ed[i].w -=
delta;
ed[i^
1].w +=
delta;
ret +=
delta;
}
}
}
return ret;
}
int main() {
n1 = read(), n2 = read(), n3 =
read();
s =
0, t = n1*
2+n2+n3+
1;
for(
int i=n1*
2+
1; i<=n1*
2+n2; i++
)
addedge(s, i, 1), addedge(i, s,
0);
for(
int i=n1*
2+n2+
1; i<=n1*
2+n2+n3; i++
)
addedge(i, t, 1), addedge(t, i,
0);
scanf("%d", &
m);
int x, y;
for(
int i=
1; i<=m; i++
) {
scanf("%d%d", &x, &
y);
addedge(y+n1*
2, x,
1), addedge(x, y+n1*
2,
0);
}
scanf("%d", &
m);
for(
int i=
1; i<=m; i++
) {
scanf("%d%d", &x, &
y);
addedge(x+n1, y+n1*
2+n2,
1), addedge(y+n1*
2+n2, x+n1,
0);
}
for(
int i=
1; i<=n1; i++
) {
addedge(i, i+n1,
1), addedge(i+n1, i,
0);
}
while (bfs()) Ans +=
Dinic(s, INF);
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9579057.html
相关资源：数据结构—成绩单生成器
