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 写法正确嘛?
模板题大水样例