WA+TLE37dinic求助!!!

P3376 【模板】网络最大流

QTcyy @ 2020-09-12 14:25:29

人都傻了啊放在其他题里都能A的在这里不行了qwq

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1000005;
const LL INF = 0x3f3f3f3f3f3f3f3f;

struct node{
    LL s;
    int to,next;
};
node que[N];

int head[N],dis[N];
bool vis[N];
int cnt=1,n,m,s,t;

inline void add(int u,int v,LL w){
    que[cnt].s=w;
    que[cnt].to=v;
    que[cnt].next=head[u];
    head[u]=cnt++;
    return;
}

inline bool bfs(){
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=1;
    q.push(s);
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (int i=head[u];i!=-1;i=que[i].next){
            int k=que[i].to;
            if (dis[k]==-1 && que[i].s){
                dis[k]=dis[u]+1;
                q.push(k);
                if (k==t)
                    return true;
            }
        }
    }
    return false;
}

LL dfs(int x,LL now){
    if (x==t)
        return now;
    LL delta=now,tmp=0;
    for (int i=head[x];i!=-1;i=que[i].next){
        int k=que[i].to;
        if (dis[k]==dis[x]+1 && que[i].s){
            tmp=dfs(k,min(delta,que[i].s));
            if (!tmp){
                dis[k]=0;
                continue;
            }

            delta-=tmp;
            que[i].s-=tmp;
            que[i^1].s+=tmp;
            if (!delta)
                break;
        }
    }
    return now-delta;
}

inline LL dinic(){
    LL ans=0,now=0;
    while (bfs())
        while (now=dfs(s,INF))
            ans+=now;
    return ans;
}

signed main(void){
    memset(head,-1,sizeof(head));
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for (int i=1;i<=m;i++){
        int a,b;LL c;
        scanf("%d%d%lld",&a,&b,&c);
        add(a,b,c);
        add(b,a,0);
    }

    printf("%lld\n",dinic());

    return 0;
}

by 幻影星坚强 @ 2020-09-12 14:29:39

要加当前弧优化才不能T,WA就不知道了()


|