我开始的代码是这样的,有问题的那一行打了注释
#include <cstdio>
#include <queue>
#include <cstring>
const int INF = 1e9;
inline int min(const int x, const int y) {return x < y ? x : y;}
std::queue<int> Q;
struct Edge {
int to, nxt, cap;
} e[200005];
int head[100005], dis[100005], cur[100005], tot = 1, s, t;
inline void AddEdge(const int u, const int v, const int cap) {
e[++ tot].to = v, e[tot].cap = cap, e[tot].nxt = head[u], head[u] = tot;
e[++ tot].to = u, e[tot].cap = 0, e[tot].nxt = head[v], head[v] = tot;
}
bool bfs() {
memcpy(cur, head, sizeof cur);
memset(dis, 0, sizeof dis);
dis[s] = 1;
Q.push(s);
while (Q.size()) {
int u(Q.front());
Q.pop();
for (int i(head[u]); i; i = e[i].nxt)
if (e[i].cap && !dis[e[i].to])
dis[e[i].to] = dis[u] + 1, Q.push(e[i].to);
}
return dis[t];
}
int dfs(const int u, int low) {
if (u == t) return low;
int res(0), flow(0);
for (int i(cur[u]); i; i = e[i].nxt) {
cur[u] = i;
if (e[i].cap && dis[u] + 1 == dis[e[i].to]) {
int v(e[i].to);
if (flow = dfs(v, min(e[i].cap, low))) {
res += flow, low -= flow;
e[i].cap -= flow, e[i ^ 1].cap += flow;
}
}
}
return res;
}
int Dinic() {
int Maxflow(0);
while (bfs()) Maxflow += dfs(s, INF);
return Maxflow;
}
int main() {
int n, p, q, m1, m2;
scanf("%d%d%d%d", &n, &p, &q, &m1);
for (int i(1); i <= n; ++ i) AddEdge(p + i, p + n + i, 1);
for (int i(1); i <= m1; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
AddEdge(v, p + u, 1);
}
scanf("%d", &m2);
for (int i(1); i <= m2; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
AddEdge(p + n + u, p + 2 * n + v, 1);
}
s = 0;
for (int i(1); i <= p; ++ i) AddEdge(s, i, 1);
t = p + n + q + 1;//这里有翁提
for (int i(1); i <= q; ++ i) AddEdge(p + 2 * n + i, t, 1);
printf("%d", Dinic());
return 0;
}
而正确的做法应该是t=p+2*n+q+1
,但是它交上去A了。
更离谱的是我在水双倍经验P1231的时候,样例过不去才发现这个问题,所以这个程序连双倍经验样例都过不去竟然能A……