为什么这份代码 long long 挂了,int 就可以A?
查看原帖
为什么这份代码 long long 挂了,int 就可以A?
602803
_qingshu_楼主2023/12/20 17:19

我把第6行与第22行的 int 改为 long long 就跑死循环了,有没有大佬可以解答一下原因?

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
struct edge{
	int to,nxt;
	int val,spend;
}e[5200010];
int head[5200010],tot=1;
void add(int u,int v,int w,int co){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	e[tot].val=w;
	e[tot].spend=co;
	head[u]=tot;
	
	e[++tot].to=u;
	e[tot].nxt=head[v];
	e[tot].val=0;
	e[tot].spend=-co;
	head[v]=tot;
}
int dis[5200010],vis[5200010],minn[5200010],pre[5200010];
bool spfa(){
	queue<int>q;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	minn[s]=INT_MAX;
	while(!q.empty()){
		int x=q.front();
		vis[x]=0;
		q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].val&&dis[v]>dis[x]+e[i].spend){
				dis[v]=dis[x]+e[i].spend;
				minn[v]=min(minn[x],e[i].val);
				pre[v]=i;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);	
				}
			}
		}
	}
	return (dis[t]!=0x3f3f3f3f);
}
int mincot,maxval;
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1,u,v,w,co;i<=m;i++){
		cin>>u>>v>>w>>co;
		add(u,v,w,co);
	}
	while(spfa()){
		int x=t;
		maxval+=minn[t];
		mincot+=dis[t]*minn[t];
		while(x!=s){
			int	i=pre[x];
			e[i].val-=minn[t];
			e[i^1].val+=minn[t];
			x=e[i^1].to;
		} 
	}
	cout<<maxval<<" "<<mincot<<endl;
}
2023/12/20 17:19
加载中...