Kobe303 @ 2021-08-30 20:07:12
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define reg register
#define il inline
const int inf = 1 << 28;
const int N = 205, M = 10005;
int head[N], ver[M], wei[M], nxt[M], d[N], now[M];
int n, m, s, t, cnt = 1;
ll maxflow;
queue<int> q;
void add(int x, int y, int z) {
ver[++cnt] = y, wei[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;
}
bool bfs() {
memset(d, 0, sizeof(d));
while (q.size()) q.pop();
q.push(s); d[s] = 1; now[s] = head[s];
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i])
if (wei[i] && !d[ver[i]]) {
q.push(ver[i]);
now[ver[i]] = head[ver[i]];
d[ver[i]] = d[x] + 1;
if (ver[i] == t) return 1;
}
}
return 0;
}
int dinic(int x, int flow) {
if (x == t) return flow;
int rest = flow, k, i;
for (i = now[x]; i && rest; i = nxt[i])
if (wei[i] && d[ver[i]] == d[x] + 1) {
k = dinic(ver[i], min(rest, wei[i]));
if (!k) d[ver[i]] = 0;
wei[i] -= k;
wei[i ^ 1] + k;
rest -= k;
}
now[x] = i;
return flow - rest;
}
int main()
{
scanf("%d%d", &n, &m);
scanf("%d%d", &s, &t);
for (int i = 1; i <= m; ++i) {
int x, y, c; scanf("%d%d%d", &x, &y, &c);
add(x, y, c), add(y, x, 0);
}
int flow = 0;
while (bfs())
while (flow = dinic(s, inf)) maxflow += flow;
printf("%lld", maxflow);
return 0;
}
这里我的
然而
by Kobe303 @ 2021-08-30 20:09:00
Update:
我现在发现
by Kobe303 @ 2021-08-30 20:10:56
Update:
我现在发现
网络流萌新,求教
by Bowen123 @ 2021-08-30 20:12:19
@Kobe303 inf是你的限定流量
就是每次增广所能跑的最大流量
如果限定的少的话固然增广次数就多
然后可能数据确实水
by Bowen123 @ 2021-08-30 20:13:01
我也才发现我的inf也才2*10^9
by KAMIYA_KINA @ 2021-08-30 20:21:55
Dinic 的实质就是你每次给一个流量让它进去跑,如果你每次给的流量足够大,能撑满一开始的水管,自然是最好的,不够大的话无非就是多跑几遍。
by Kobe303 @ 2021-08-30 20:23:25
@KAMIYA_KINA
谢谢啦,刚学网络流,可能会有一些比较无脑的问题
by Kobe303 @ 2021-08-30 20:23:52
@Bowen123
谢谢啦