Dinic TLE91分是什么原因啊
查看原帖
Dinic TLE91分是什么原因啊
754746
Resolute_Faith楼主2022/7/24 14:30

以前一直打EK,今天改一下Dinic的板子,先63 MLE了,然后改了一下dfs就变成91 TLE了,应该怎么改啊

//【模板】Dinic最大流
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int M=5e3+5;
const int inf=2147400000;
struct edge{int to,nxt,l,cst;}a[N];
int n,m,s,t,cnt=1,head[N],dis[M],now[M],ans,ansy;
bool vis[M];
void add(int x,int y,int z,int c){
	a[++cnt].to=y;
	a[cnt].nxt=head[x];
	a[cnt].l=z;
    a[cnt].cst=c;
	head[x]=cnt;
}
int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<48||ch>57){
        if(ch=='-') y=0;
        ch=getchar();
    }while(ch>47&&ch<58) x=x*10+ch-48,ch=getchar();
    return y?x:-x;
}
bool SPFA(){
	for(register int i=1;i<=n;i++) dis[i]=inf,vis[i]=false;
	queue<int> q;
	q.push(s),dis[s]=0,now[s]=head[s],vis[s]=true;
	while(!q.empty()){
		int x=q.front();q.pop();
        vis[x]=false;
		for(register int i=head[x];i;i=a[i].nxt){
			int y=a[i].to;
			if(a[i].l>0&&dis[y]>dis[x]+a[i].cst){
				dis[y]=dis[x]+a[i].cst;
				now[y]=head[y];
				if(!vis[y]){
                    vis[y]=true;
                    q.push(y);
                }
			}
		}
	}
    if(dis[t]!=inf) return true;
	return false;
}
int dfs(int x,int flow){
	if(x==t) return flow;
	int ans=0;
	for(register int i=now[x];i&&flow;i=a[i].nxt){
		int y=a[i].to;
        if(vis[y]) continue;
		now[x]=i;
		if(a[i].l>0&&dis[y]==dis[x]+a[i].cst){
            vis[y]=true;
			int k=dfs(y,min(flow,a[i].l));
			a[i].l-=k,a[i^1].l+=k;
			if(!k) dis[y]=inf;
			ans+=k,flow-=k;
            ansy+=a[i].cst*k;
		}
	} 
	return ans;
}
signed main(){
	scanf("%d %d %d %d",&n,&m,&s,&t);
	for(register int i=1;i<=m;i++){
	    int x,y,z,c;
	    x=read(),y=read(),z=read(),c=read();
	    add(x,y,z,c);
	    add(y,x,0,-c);
	}
	while(SPFA()) ans+=dfs(s,inf);
	printf("%d %d",ans,ansy);
}
2022/7/24 14:30
加载中...