以前一直打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);
}