求助神奇的WA点?
查看原帖
求助神奇的WA点?
186068
我怂了楼主2023/10/24 17:20

下列程序,将 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&&sum;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;
} 
2023/10/24 17:20
加载中...