求助关于网络流
查看原帖
求助关于网络流
563650
haochengw920楼主2024/8/8 13:50

rt , 下面是我写的 ISAP 代码:

#include<cstdio>
#include<algorithm>
#define INF (0x3f3f3f3f)
using namespace std;

const int MAXN = 505, MAXM = 200005;

int n, f, d;
struct edge {
	int to, nex, dis;
}e[MAXM]; int idx = 1, head[MAXN];
inline void add(int u, int v, int w) {
	e[++ idx].to = v;
	e[idx].dis = w;
	e[idx].nex = head[u];
	head[u] = idx;
}
inline void add_edge(int u, int v, int w) {
	add(u, v, w); add(v, u, 0);
}

int S, T, ans;
int dep[MAXN], nw[MAXN];
int flag, gap[MAXN];
inline int dfs (int u, int sum) {
	if (u == T) return sum;
	int res = 0;
	for (int i = nw[u]; i && sum; i = e[i].nex) {
		int v = e[i].to; nw[u] = i;
		if (!e[i].dis || dep[u] != dep[v] + 1) 
			continue;
		int k = dfs(v, min(sum, e[i].dis));
		e[i].dis -= k, e[i ^ 1].dis += k;
		res += k, sum -= k;
	}
	if (!sum) return res;
	nw[u] = head[u];
	int mn = T + 10;
	for (int i = head[u]; i; i = e[i].nex)
		if (e[i].dis) mn = min(mn, dep[e[i].to] + 1);
//	if (dep[u] == mn) return res;
	if (!--gap[dep[u]]) flag = 0;
	dep[u] = mn, ++ gap[dep[u]]; 
	return res; 
} 
inline void ISAP() {
	ans = 0, flag = 1;
	for (int i = 1; i <= T; ++ i) 
		nw[i] = head[i], gap[i] = dep[i] = 0;
	gap[0] = T;
	while (flag) ans += dfs(S, INF);
}

int main()
{
	scanf ("%d%d%d", &n, &f, &d);
	S = 1, T = (n << 1) + f + d + 2;
	for (int i = 1; i <= f; ++ i) 
		add_edge(S, i + 1, 1);
	for (int i = 1; i <= n; ++ i) 
		add_edge(f + i + 1, n + f + i + 1, 1);
	for (int i = 1; i <= d; ++ i) 
		add_edge((n << 1) + f + i + 1, T, 1);
	for (int i = 1; i <= n; ++ i) {
		int fn, dn;
		scanf ("%d%d", &fn, &dn);
		for (int j = 1; j <= fn; ++ j) {
			int x; scanf ("%d", &x);
			add_edge(x + 1, f + i + 1, 1);
		} for (int j = 1; j <= dn; ++ j) {
			int x; scanf ("%d", &x);
			add_edge(n + f + i + 1, (n << 1) + f + x + 1, 1);
		}
	} ISAP();
	return printf ("%d\n", ans), 0;
}

其中,在代码中注释掉 if (dep[u] == mn) return res; 就能通过,不注释就会且仅会在样例 TLE

但是我不注释却通过了网络流模板题。

请问不注释的 ISAP 代码有什么问题?注释后我的 ISAP 写法正确嘛?

模板题大水样例

2024/8/8 13:50
加载中...