我怂了 @ 2023-10-24 17:20:41
下列程序,将 inf
设为1e18就WA,但是设为2005020600就会成功AC,为啥啊qwq
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+2e4;
const ll inf=2005020600;
int n,m,s,t,u,v;
ll w,ans=0,dis[maxn];
struct edge{
int to,net;
ll val;
}e[maxn];
int tot=1;
int last[maxn],now[maxn];
void add(int x,int y,ll w){
e[++tot].to=y;
e[tot].val=w;
e[tot].net=last[x];
last[x]=tot;
e[++tot].to=x;
e[tot].val=0;
e[tot].net=last[y];
last[y]=tot;
}
bool bfs(){
for(int i=1;i<=n;i++){
dis[i]=inf;
}
queue<int> q;
q.push(s);
dis[s]=0;
now[s]=last[s];
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=last[x];i;i=e[i].net){
int v=e[i].to;
if(e[i].val>0&&dis[v]==inf){
q.push(v);
now[v]=last[v];
dis[v]=dis[x]+1;
if(v==t){
return true;
}
}
// q.push()
}
}
return 0;
}
int dfs(int x,ll sum){
if(x==t){
return sum;
}
ll k,res=0;
for(int i=now[x];i&∑i=e[i].net){
now[x]=i;
int v=e[i].to;
if(e[i].val>0&&(dis[v]==dis[x]+1)){
k=dfs(v,min(sum,e[i].val));
if(k==0){
dis[v]=inf;
}
e[i].val-=k;
e[i^1].val+=k;
res+=k;
sum-=k;
}
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
while(bfs()){
ans+=dfs(s,inf);
}
cout<<ans;
}