16分,后面全TLE了
查看原帖
16分,后面全TLE了
560291
the_Dream_Chaser楼主2023/12/1 17:49

RT,求大佬指点

#include<bits/stdc++.h>
using namespace std;
const int MAXN=520020;
const int M=2510;

int n,m,s,t,u,v;
long long w,dis[MAXN];
long long head[MAXN],pre[MAXN],vis[MAXN],tot=1;
long long flag[M][M];
long long ans;
struct Edge{
	int to,next;
	long long val;
}e[MAXN];
void add(int u,int v,long long w){
	e[++tot].to=v;
	e[tot].val=w;
	e[tot].next=head[u];
	head[u]=tot;
	e[++tot].to=u;
	e[tot].val=0;
	e[tot].next=head[v];
	head[v]=tot;
}
long long bfs(){
	for(long long i=1;i<=n;i++)vis[i]=0;
	queue<int> q;
	//cout<<s<<" ";
	q.push(s);
//	cout<<q.front()<<" ";
	vis[s]=1;
	dis[s]=MAXN<<2;
	
	while(!q.empty()){
		int x=q.front();
		q.pop();
//		cout<<1<<" "<<x<<endl;
		for(long long i=head[x];i;i=e[i].next){
			if(e[i].val==0) continue; 
			int v=e[i].to;
			if(vis[v]==1) continue;  //没有访问
			vis[v]=1;
			dis[v]=min(dis[x],e[i].val);
			pre[v]=i;  //记录前驱,方便修改
			if(v==t) return 1; //找到一条路 
			q.push(v);
			
		}
	}
	return 0;
}
void update(){
	int x=t;
	while(x!=s){
		int k=pre[x];
		e[k].val-=dis[t];
		e[k^1].val+=dis[t];
        x=e[k^1].to;
	}
	ans+=dis[t];
}
int main(){
	cin>>n>>m>>s>>t;
	for(long long i=1;i<=m;i++){
		cin>>u>>v>>w;
		if(flag[u][v]==0){
			add(u,v,w);
			flag[u][v]=tot;
		}
		else{	
			e[flag[u][v]-1].val+=w;
		}
	}
	while(bfs()){
		update();
	}
	cout<<ans;
	return 0;	
} 

2023/12/1 17:49
加载中...