求助dinic蜜汁MLE
查看原帖
求助dinic蜜汁MLE
263651
_YangZj楼主2021/8/19 10:02
#include<bits/stdc++.h>
#define memu(a) memset(a,0x3f,sizeof(a))
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
using namespace std;
const int N=5e3+5,M=5e4+5,inf=0x3f3f3f3f;

int n,m,s,t,u,v,w,k;
int hd[N],to[M<<1],e[M<<1],c[M<<1],ne[M<<1],tc=1;
int hed,tl,Q[N<<5],pre[N],incf[N],d[N],cur[N];
ll maxflow,mincost;
bool inq[N];

inline void add(int,int,int,int);
inline void EK();
inline bool bfs();
inline int dfs(int,int);

int main() {
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++) scanf("%d%d%d%d",&u,&v,&w,&k), add(u,v,w,k);
    EK();
    printf("%lld %lld\n",maxflow,mincost);
    return 0;
}

inline void add(int x,int y,int z,int a) {
    to[++tc]=y; e[tc]=z; c[tc]=a; ne[tc]=hd[x]; hd[x]=tc;
    to[++tc]=x; e[tc]=0; c[tc]=-a; ne[tc]=hd[y]; hd[y]=tc;
}

inline void EK() { while(bfs()) dfs(s,inf); }

inline bool bfs() {
    hed=1; tl=0;
    memu(d); mem(inq); memcpy(cur,hd,sizeof(cur)); incf[s]=inf;
    Q[++tl]=s; inq[s]=true; d[s]=0;
    while(hed<=tl) {
        int x=Q[hed++];
        inq[x]=false;
        for(int i=hd[x],y;i;i=ne[i]) 
            if(e[i] && d[y=to[i]]>d[x]+c[i]) {
                d[y]=d[x]+c[i]; pre[y]=i; incf[y]=min(incf[x],e[i]);
                if(!inq[y]) Q[++tl]=y, inq[y]=true;
            }
    }
    return d[t]!=inf;
}

inline int dfs(int x,int flow) {
    if(!(x^t)) { maxflow+=flow; mincost+=d[t]*flow;  return flow; }
    int used=0,now;
    for(int i=cur[x],y;i;i=ne[i]) {
        cur[x]=i;
        if(!e[i] || d[y=to[i]]!=d[x]+c[i]) continue;
        now=dfs(y,min(flow-used,e[i]));
        if(!now) continue;
        used+=now; e[i]-=now; e[i^1]+=now;
        if(!(used^flow)) break;
    }
    return used;
}
2021/8/19 10:02
加载中...