3a51_ @ 2022-06-02 15:33:24
萌新初学网络流,参考了下题解。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod1=998244353;
const int Mod2=1000000007;
const int Inf=1e18;
int gcd(int a,int b){return __gcd(a,b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
const int N=205;
const int M=10005;
int to[M],nxt[M],val[M],lst[N],cnt,vis[N],n,m,s,t;
void add(int u,int v,int w){
to[++cnt]=v;
val[cnt]=w;
nxt[cnt]=lst[u];
lst[u]=cnt;
}
int dfs(int u,int now){
if(u==t) return now;
vis[u]=1;
for(int i=lst[u];i!=0;i=nxt[i]){
int v=to[i];
if(vis[v]==1) continue;
int p=dfs(v,min(now,val[i]));
if(p>0){
val[i]-=p;
val[i+1]+=p;
return p;
}
}
return 0;
}
void Solve(){
//coding here...
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,0);
}
int ans=0;
int p=dfs(s,Inf);
while(p>0){
memset(vis,0,sizeof(vis));
ans+=p;
p=dfs(s,Inf);
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
int _;
//cin>>_;
_=1;
while(_--){
Solve();
}
return 0;
}
//STO 来看我程序的人 Orz
by YamadaRyou @ 2022-06-02 15:37:54
@Tothetime_tolife FF 复杂度不对吧()
by 3a51_ @ 2022-06-02 15:38:59
@cxy2022 但是只会FF
by 3a51_ @ 2022-06-02 15:39:11
不应该AC一部分TLE一部分吗
by YamadaRyou @ 2022-06-02 15:43:52
@Tothetime_tolife 您的inf爆int了。。。
by YamadaRyou @ 2022-06-02 15:44:33
草,define int long long了啊,那我再看看/kk
by 3a51_ @ 2022-06-02 15:44:37
@cxy2022 有宏定义
by rsdbk_husky @ 2022-06-02 15:45:28
@Tothetime_tolife 反向边错了,i
的反向边是 i^1
,而且用 ++cnt
的话 cnt
应初始化为奇数。
by 3a51_ @ 2022-06-02 15:45:58
@rsdbk_husky thx
by 3a51_ @ 2022-06-02 15:47:32
还是WA/kk
by 3a51_ @ 2022-06-02 15:49:55
谢谢大家找到问题了忘了回溯