@[david0911](/user/685536) 您这 `Dinic` 写的怪怪的。复杂度还带了一个 `SPFA` 。建议改几下。
by char_cha_ch @ 2022-12-20 10:44:07
@[kirihara233](/user/701221) 下载样例发现输出是对的，但测评就是WA
by david0911 @ 2022-12-20 10:57:53
@[david0911](/user/685536) 不用判重，哥。
by char_cha_ch @ 2022-12-20 10:59:05
@[kirihara233](/user/701221) 但是题目中说 **“不保证给出的图没有重边”**
by david0911 @ 2022-12-20 11:03:27
@[david0911](/user/685536) 但是重边会影响答案吗？
by char_cha_ch @ 2022-12-20 11:08:42
@[david0911](/user/685536) 我就没判啊。
```cpp
#include<cstdio>
#define N 1009
#define M 200009
struct node
{
int v, w, nxt;
}e[M];
int head[N], cnt = 1;
inline void add(int u, int v, int w)
{
e[++ cnt].v = v, e[cnt].w = w, e[cnt].nxt = head[u], head[u] = cnt;
}
int dis[N], now[N];
#include<queue>
using std::queue;
#include<cstring>
using std::memset;
int s, t;
inline bool bfs()
{
memset(dis, -1, sizeof dis);
queue < int > q;
q.push(s);
dis[s] = 0;
register int u, v, i;
now[s] = head[s];
while (!q.empty())
{
u = q.front();
q.pop();
for (i = now[u];i;i = e[i].nxt)
{
v = e[i].v;
if (e[i].w > 0 && dis[v] == -1)
{
dis[v] = dis[u] + 1;
now[v] = head[v];
if (v == t)
return 1;
q.push(v);
}
}
}
return 0;
}
inline int min(int a, int b)
{
return a < b ? a : b;
}
int dfs(register int u, register int flow = 1e9)
{
if (u == t)
return flow;
register int v, w, i, k, lost = flow;
for (i = now[u];i && lost;i = e[i].nxt)
{
now[u] = i;
v = e[i].v, w = e[i].w;
if (w > 0 && dis[v] == dis[u] + 1)
{
k = dfs(v, min(lost, w));
if (!k)
{
dis[v] = -1;
continue;
}
lost -= k;
e[i].w -= k;
e[i ^ 1].w += k;
}
}
return flow - lost;
}
inline int read()
{
register int ret = 0;
register bool f = 1;
register char ch = getchar();
while (ch < '0' || ch > '9')
(ch == '-') ? f = 0 : 0, ch = getchar();
while (ch >= '0' && ch <= '9')
ret = (ret << 1) + (ret << 3) + (ch ^ 48), ch = getchar();
return f ? ret : -ret;
}
int main()
{
register int n, n1 = read(), n2 = read(), m = read(), i, u, v, ans = 0;
n = n1 + n2;
s = 0, t = n + 1;
for (i = 1;i <= m;++ i)
u = read(), v = read() + n1, add(u, v, 1), add(v, u, 0);
for (i = 1;i <= n1;++ i)
add(0, i, 1), add(i, 0, 0);
for (i = n1 + 1;i <= n1 + n2;++ i)
add(i, t, 1), add(t, i, 0);
while (bfs())
ans += dfs(s);
printf("%d", ans);
return 0;
}
```
by char_cha_ch @ 2022-12-20 11:09:52
@[david0911](/user/685536) 你自己想想，连 $s$ 连 $t$ 相当于有个限制条件，保证了一个点只选了一次。你即使重边也不会流第二次啊。
by char_cha_ch @ 2022-12-20 11:11:34
@[kirihara233](/user/701221) ~~我不到啊~~删掉判重还是爆零QAQ
by david0911 @ 2022-12-20 11:11:59
@[david0911](/user/685536) 那看看出了什么错。感觉你写的很特别。这个有点难改。
by char_cha_ch @ 2022-12-20 11:12:46
@[kirihara233](/user/701221) 可能是我写的太丑了QAQ，我再改改，谢谢你
by david0911 @ 2022-12-20 11:16:38