关于ub
查看原帖
关于ub
369041
bdfs_then_csdn楼主2023/3/23 19:32

复习了一下然后样例没过,看了10min没看出来问题然后同学让交一发直接过了,感觉是ub的事,但是不知道哪里qwq

#include<bits/stdc++.h>
using namespace std;
int s,t,n,m,b[5001][5001],h[100001],cnt=1,vis[100001],p[100001];
long long ans,dis[100001];struct sss{int to,next;long long val;}e[100001];
void add(int u,int v,int w){e[++cnt].to=v;e[cnt].next=h[u],e[cnt].val=w;h[u]=cnt;e[++cnt].to=u;e[cnt].next=h[v],e[cnt].val=0;h[v]=cnt;}
int ek(){
	for(int i=1;i<=n;i++)vis[i]=0;
	queue<int>q;q.push(s);dis[s]=2007032600;vis[s]=1;
	while(!q.empty()){
		int v=q.front();
		q.pop();
		for(int i=h[v];i;i=e[i].next){
			if(e[i].val==0)continue;
			int tt=e[i].to;
			if(vis[tt]==1)continue;
			dis[tt]=min(dis[v],e[i].val);
			p[tt]=i;q.push(tt);vis[tt]=1;
			if(tt==t)return 1;
		}
	}
	return 0;
}
void calc(){
	int x=t;
	while(x!=s){int v=p[x];e[v].val-=dis[t];e[v^1].val+=dis[t];x=e[v^1].to;}
	ans+=dis[t];
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%lld",&u,&v,&w);
		if(!b[u][v])add(u,v,w),b[u][v]=cnt;
		else e[b[u][v]-1].val+=w;
	}
	while(ek())calc();
	cout<<ans;
}
2023/3/23 19:32
加载中...