JK_LOVER @ 2020-07-27 09:39:09
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
const int N = 1800100;
struct Dinic{
int head[N],cur[N],dis[N],s,t,n,cnt;
struct E{int cap,flow,to,nxt;}e[N];
void add(int x,int y,int cap)
{
e[++cnt].nxt = head[x];
e[cnt].flow = 0;
e[cnt].cap = cap;
e[cnt].to = y;
head[x] = cnt;
}
int Dfs(int x,int a,int t)
{
if(x == t || a == 0) return a;
int f = 0,flow = 0;
for(int i = cur[x];~i;i = e[i].nxt)
{
int y = e[i].to;
if(dis[x] + 1 == dis[y] && ((f = Dfs(y,min(a,e[i].cap - e[i].flow),t))>0))
{
a -= f;
flow += f;
e[i].flow += f;
e[i^1].flow -= f;
cur[x] = e[i].nxt;
if(a == 0) break;
}
}
if(flow == 0) dis[x] = 0;
return flow;
}
bool Bfs(int s,int t)
{
queue<int> Q;
memset(dis,0,sizeof(dis));
Q.push(s);dis[s] = 1;
while(Q.size())
{
int x = Q.front();Q.pop();
for(int i = head[x];~i;i = e[i].nxt)
{
int y = e[i].to;
if(e[i].cap > e[i].flow && !dis[y])
{
dis[y] = dis[x] + 1;
Q.push(y);
if(dis[t])
{
return true;
}
}
}
}
return false;
}
}MaxFlow;
int n,m,s,t;
long long maxflow = 0;
signed main()
{
n = MaxFlow.n = read();m = read();
s = MaxFlow.s = read();t = MaxFlow.t = read(),MaxFlow.cnt = -1;
memset(MaxFlow.head,-1,sizeof(MaxFlow.head));
for(int i = 1;i <= m;i++)
{
int a = read(),b = read(),cap = read();
MaxFlow.add(a,b,cap);
MaxFlow.add(b,a,0);
}
while(MaxFlow.Bfs(s,t))
{
for(int i = 1;i <= MaxFlow.n;i++) MaxFlow.cur[i] = MaxFlow.head[i];
maxflow += MaxFlow.Dfs(s,0x3f3f3f3f,t);
}
cout<<maxflow<<endl;
}
by a___ @ 2020-07-27 09:54:56
您dfs里 cur[x]=e[i].nxt
应该放在 if
外面改成 cur[x]=i
吧
by 樱巫女Official @ 2020-07-27 09:57:23
cur[x] = e[i].nxt;
放if(a == 0) break;
后面
by a___ @ 2020-07-27 09:58:32
@JK_LOVER
by a___ @ 2020-07-27 09:59:56
额,楼上说的应该也可以
by JK_LOVER @ 2020-07-27 10:04:34
@a___ @樱巫女Official 谢谢
by JK_LOVER @ 2020-07-27 10:06:03
@樱巫女Official 为什么放在后面是对的啊/kk
by a___ @ 2020-07-27 10:10:35
@JK_LOVER 因为最后一次次流出可能没流满
by JK_LOVER @ 2020-07-27 10:12:58
@a___ 那就是我可能还有残留网络,而我直接判掉了,哦,谢谢,太感谢了