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 Raymondzll @ 2022-03-26 21:33:04
@quanjun longlong的问题吧,不确定
by ningago @ 2022-03-26 21:33:47
@quanjun
你用了e[i^1].f
,所以01,23是一组,ecnt = 1就行了(吧)
by 7KByte @ 2022-03-26 21:34:41
@ningago 他的边是0开始编号的好吧
by ningago @ 2022-03-26 21:35:20
@7KByte 我瞎了,++idx
人再此
by 7KByte @ 2022-03-26 21:36:25
@quanjun long long的问题,还有连边时反向边的容量应该是0
by wkywkywky @ 2022-03-26 21:40:28
@7KByte 加了只有91
by Refined_heart @ 2022-03-26 21:43:39
@quanjun 加上当前弧过了
by quanjun @ 2022-03-26 21:46:11
@7KByte 谢谢大佬,之前提交过这道题,发现这次数据又加强了,原来是反边为0的问题,改过来之后有一组数据TLE了,不过已经解决了我的疑问,十分感谢,5元红包私聊您哈
by quanjun @ 2022-03-26 21:46:58
@Refined_heart 请问什么是当前弧哈,大佬可以发一下你的代码吗?
by Refined_heart @ 2022-03-26 21:47:23
@quanjun 刚刚已经给你私信过去了