7KByte @ 2020-06-17 16:53:01
Rt,估计以前写的都是错的,但是为啥从没有出现过问题。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 205
#define M 5005
typedef long long ll;
using namespace std;
int h[N],tot=1;
struct edge{
int to,nxt,cap;
}e[M<<1];
void add(int x,int y,int z){
e[++tot].nxt=h[x];h[x]=tot;e[tot].cap=z;e[tot].to=y;
}
int n,m,s,t,d[N],cur[N];
queue<int>q;
bool bfs(){
memset(d,0,sizeof(d));
d[s]=1;q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
cur[x]=h[x];
for(int i=h[x];i;i=e[i].nxt)
if(e[i].cap&&!d[e[i].to])
d[e[i].to]=d[x]+1,q.push(e[i].to);
}
return d[t];
}
int dfs(int x,int flow){
if(x==t)return flow;
int res=flow;
for(int &i=cur[x];i;i=e[i].nxt){
if(!res)return flow;
if(e[i].cap&&d[x]+1==d[e[i].to]){
int now=dfs(e[i].to,min(res,e[i].cap));
if(!now)d[e[i].to]=1;
else{
e[i].cap-=now;
e[i^1].cap+=now;
res-=now;
}
}
}
return flow-res;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
rep(i,1,m){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,0);
}
ll ans=0;
while(bfs())ans+=dfs(s,0x7fffffff);
printf("%lld\n",ans);
return 0;
}
by smarthehe @ 2020-06-17 17:43:43
@几何之舞丶 Undefined Behavior
by smarthehe @ 2020-06-17 17:46:03
@Inf_Voltage
这个的区别是,如果你在循环一开始写,可能这条边没有流满你却进了下一条边,把下一条边当成了当前弧。前一条边还没有流满就废了。
by WrongAnwser @ 2020-06-19 09:11:29
@smarthehe
感谢大佬,如果没看到您的回复我估计这辈子写的都是假的Dinic了(原来loj模板题时间跑30ms才是正常的我原来都跑的是500ms以上)