Dinik+SPFA #8~11 MLE 求助
查看原帖
Dinik+SPFA #8~11 MLE 求助
222865
迟暮天复明心華楼主2024/3/2 13:46

看了讨论版但是似乎也查不出任何问题。。。

主体部分基本是贺的 oiwiki

#include<bits/stdc++.h>
using namespace std;
//#define int long long
constexpr int INF=1e9;

struct edge{
  int to,nxt,flow,cost;
}e[200010];
int cnt=1,head[200010],now[200010],dis[200010],vis[200010],n,m,s,t,res;
void add(int u,int v,int w,int c){
  e[++cnt]={v,head[u],w,c};
  head[u]=cnt;
  e[++cnt]={u,head[v],0,-c};
  head[v]=cnt;
}
int spfa(){
  for(int i=0;i<=n;++i)dis[i]=INF,now[i]=head[i],vis[i]=0;
  queue<int>q;q.push(s),dis[s]=0,vis[s]=1;
  while(!q.empty()){
    int u=q.front();q.pop();
    vis[u]=0;
    for(int i=head[u];i;i=e[i].nxt)if(e[i].flow){
      int v=e[i].to;
      if(dis[v]>dis[u]+e[i].cost){
        dis[v]=dis[u]+e[i].cost;
        if(!vis[v])q.push(v),vis[v]=1;
      }if(v==t)return 1;
    }
  }return 0;
}
inline int dfs(int u,int f){
  if(u==t||!f)return f;
  int sum=0;vis[u]=1;
  for(int i=now[u];i;i=e[i].nxt)if(e[i].flow){
    int v=e[i].to;now[u]=i;
    if(dis[v]==dis[u]+e[i].cost){
      int k=dfs(v,min(f,e[i].flow));
      if(!k){dis[v]=0;continue;}
      e[i].flow-=k,e[i^1].flow+=k;
      sum+=k,f-=k,res+=e[i].cost*k;
    }
  }vis[u]=0;return sum;
}
signed main(){
  cin>>n>>m>>s>>t;
  for(int i=1;i<=m;++i){
    int u,v,w,c;cin>>u>>v>>w>>c;add(u,v,w,c);
  }int ans=0;while(spfa())ans+=dfs(s,INT_MAX);
  cout<<ans<<' '<<res;
  return 0;
}
2024/3/2 13:46
加载中...