Chancylaser @ 2021-07-21 18:04:30
#include<iostream>//网络最大流
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const long long maxn=5005;
long long n,m;
long long s,t;
long long a,b,c;
struct edge{
long long e,f;
long long next;
long long op;
}ed[maxn<<1];
long long first[maxn];
long long en;
void add(long long s,long long e,long long f){
en++;
ed[en].next=first[s];
first[s]=en;
ed[en].e=e;
ed[en].f=f;
en++;
ed[en].next=first[e];
first[e]=en;
ed[en].e=s;
ed[en].f=0;
ed[en].op=en-1;
ed[en-1].op=en;
return;
}
long long depth[100005];
long long dfs(long long now,long long flow){
if(now==t) return flow;
long long ans=0;
for(register int i=first[now];i!=0;i=ed[i].next){
long long e=ed[i].e, f=ed[i].f , op=ed[i].op;
if(f!=0&&flow!=0&&depth[e]>depth[now]){
long long delta=dfs(e,min(f,flow));
ed[i].f-=delta;
ed[op].f+=delta;
flow-=delta;
ans+=delta;
}
}
return ans;
}
bool bfs(long long s){
queue<long long> q;
q.push(s);
memset(depth,0,sizeof(depth));
depth[s]=1;
while(q.size()){
long long now=q.front();
q.pop();
for(register int i=first[now];i!=0;i=ed[i].next){
long long e=ed[i].e , f=ed[i].f;
if(depth[e]==0&&f!=0){
depth[e]=depth[now]+1;
q.push(e);
}
}
}
return depth[t]!=0;
}
long long dinic(){
long long ans=0;
while(bfs(s))
ans+=dfs(s,1e12+19);
return ans;
}
int main(){
//freopen("qwq.txt","r",stdin);
cin>>n>>m>>s>>t;
for(register int i=1;i<=m;i++){
cin>>a>>b>>c;
add(a,b,c);
}
cout<<dinic();
return 0;
}
这是我的代码,有一个点tle了,2天了,还没有调出来,有没有神仙给我看一下呀?
by 幻影星坚强 @ 2021-07-21 18:07:39
要加当前弧优化
by michael_song @ 2021-07-22 08:20:27
@幻影星坚强 我交的时候没优化就过了
by 幻影星坚强 @ 2021-07-22 08:25:28
@michael_song 可是你加了
by michael_song @ 2021-07-22 08:34:16
@幻影星坚强 ? 好吧可能我一开始学的就是要加的 离谱