wfawfas @ 2023-10-21 18:37:57
下面是源代码,求助
怎么调#9#10都过不了
#include<iostream>
#include<climits> //‘INT_MAX’ is defined in header ‘<climits>’
#include<cstring> //‘memset’ is defined in header ‘<cstring>’
#include<queue>
using namespace std;
#define Max 100000
#define LL long long
struct edge
{
int next; //同起点的边,连成一条链子
int to; //边指向的点
LL w; //边的权值
}e[Max];
int head[Max] = { 0 };
int cnt = 0;
void add_edge(int u, int v, LL w)
{
cnt++;
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u]; //初始时,链子最后的元素.next=0
head[u] = cnt;
//建立反向边,使其编号为原边加1
cnt++;
e[cnt].to = u;
e[cnt].w = 0;
e[cnt].next = head[v];
head[v] = cnt;
}
int n; int m;
int s, t;
int lv[Max];
int cur[Max];
int bfs() //bfs进行分层
{
memset(lv, -1, sizeof(lv));
lv[s] = 0;
for (int i = 1; i <= n; i++)
cur[i] = head[i];
queue<int> q;
q.push(s);
while (!q.empty())
{
int p = q.front();
q.pop();
for (int eg = head[p]; eg; eg = e[eg].next)
{
int to = e[eg].to;
LL val = e[eg].w;
if (val > 0 && lv[to] == -1)
{
lv[to] = lv[p] + 1;
q.push(to);
}
}
}
return lv[t] != -1; //判断是否能到达终点
}
LL dfs(int p, LL flow)
{
if (p == t)
return flow;
LL rest = flow;
for (int eg = cur[p]; eg&&rest; eg = e[eg].next) //对该点起始的所有边进行遍历
{
cur[p] = eg; //把多次DFS弄到一起
int to = e[eg].to;
LL val = e[eg].w;
if (val>0&&lv[to]==lv[p]+1) //往深处DFS
{
LL c = dfs(to, min(val,rest));
rest -= c; //该点所能流过的流量减少,接着在寻找该点的其他边
e[eg].w -= c;
e[eg + 1].w += c; //保证反向边紧接着正向边建立
//构造残量网络
}
}
return flow - rest;
}
LL Dinic()
{ LL Max_Flow = 0; while (bfs()) { Max_Flow += dfs(s, LONG_MAX); } return Max_Flow; } int main() { cin >> n >> m; cin >> s >> t; for (int i = 0; i < m; i++) { int u, v; LL w; cin >> u >> v >> w; bool temp = true; for (int eg = head[u]; eg; eg = e[eg].next) //对该点起始的所有边进行遍历 if (e[eg].to == v) { e[eg].w += w; temp = false; break; } if (temp) add_edge(u, v, w); } cout << Dinic(); return 0; }
by wfawfas @ 2023-10-21 18:39:01
已经处理过重边了