数据过水
查看原帖
数据过水
361308
Stinger楼主2021/4/27 11:51

我开始的代码是这样的,有问题的那一行打了注释

#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……

2021/4/27 11:51
加载中...