quanjun @ 2022-03-26 21:30:25
按照《ACM国际大学生程序设计竞赛.算法与实现》第89页的dinic模板实现的(稍微改动了一些,但是应该也没有啥问题啊)。求大佬帮忙看一下我的代码实现,并私信我微信或者QQ,我会给第一位解答对的大佬转5元红包,万分感谢!
下面是代码:
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9, maxn = 202, maxm = 10010;
struct Edge {
int v, f, nxt;
} e[maxm];
int n, m, src, sink, head[maxn], ecnt;
void init() {
ecnt = 0;
memset(head, -1, sizeof(int)*(n+1));
}
void addedge(int u, int v, int c) {
e[ecnt] = {v, c, head[u]}; head[u] = ecnt++;
e[ecnt] = {u, c, head[v]}; head[v] = ecnt++;
}
queue<int> que;
int dis[maxn];
bool bfs() {
while (!que.empty())
que.pop();
memset(dis, -1, sizeof(int)*(n+1));
dis[src] = 0;
que.push(src);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; i != -1; i = e[i].nxt) {
int v = e[i].v;
if (e[i].f && dis[v]==-1) {
dis[v] = dis[u] + 1;
que.push(v);
}
}
}
return dis[sink] != -1;
}
int dfs(int u, int delta) {
if (u == sink)
return delta;
int res = 0;
for (int i = head[u]; i != -1 && delta; i = e[i].nxt) {
int v = e[i].v, f = e[i].f;
if (f && dis[v] == dis[u] + 1) {
int dd = dfs(v, min(delta, f));
e[i].f -= dd;
e[i^1].f += dd;
delta -= dd;
res += dd;
}
}
return res;
}
int maxflow() {
int res = 0;
while (bfs())
res += dfs(src, inf);
return res;
}
int main() {
cin >> n >> m >> src >> sink;
init();
while (m --) {
int u, v, w;
cin >> u >> v >> w;
addedge(u, v, w);
}
cout << maxflow() << endl;
return 0;
}
by quanjun @ 2022-03-26 21:48:06
@Refined_heart 感谢!