Dinic死循环

optimize_2 @ 2020-05-25 20:10:21

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

int n,m,s,t,cnt,first[100010],next[100010],to[100010],w[10010];
bool vst[100010];

void add(int u,int v,int w2) {
    cnt++;
    w[cnt]=w2;
    to[cnt]=v;
    next[cnt]=first[u];
    first[u]=cnt;
}

int dep[100010];

bool bfs() {
    memset(dep,0,sizeof(dep));
    queue<int>q;
    q.push(1);
    dep[1]=1;
    while(!q.empty()) {
        int e;
        int head=q.front();
        q.pop();
        for(e=first[head];e;e=next[e]) {
            int v=to[e];
            if(dep[v]==0&&w[e]>0) {
                dep[v]=dep[head]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=0;
}

int dinic(int now,int flow) {
    if(now==t) {
        return flow;
    }
    int out=0;
    for(int e=first[now];e&&flow;e=next[e]) {
        int v=to[now];
        if(dep[e]!=dep[now]+1) continue;
        int outnow=dinic(v,min(w[e],out));
        flow-=outnow;
        w[e]-=outnow;
        w[e^1]+=outnow;
        out+=outnow;
    }
    if(out==0) dep[now]=0;
    return out;
}

int main() {
    int ans=0;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) {
        int u2,v2,w2;
        cin>>u2>>v2>>w2;
        add(u2,v2,w2);
        add(v2,u2,0);
    }
    while(bfs()) {
        ans+=dinic(s,1e9+114514);
    }
    cout<<ans;
}

by FZzzz @ 2020-05-25 20:13:10

@optmize_2 您 dfs 里判的是 dep[e]……

by FZzzz @ 2020-05-25 20:13:20

失踪人口回归/fad

by __gcd @ 2020-05-25 20:13:34

@optmize_2 源点是？

by lgswdn_SA @ 2020-05-25 20:21:42

cnt 初始化为1？

by Flandre_495 @ 2020-05-25 20:35:19

@optmize_2 cnt初值赋成1

by optimize_2 @ 2020-06-27 10:14:39

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

int n,m,s,t,cnt,first[100010],nxt[100010],to[100010],w[10010];
bool vst[100010];

void add(int u,int v,int w2) {
    cnt++;
    w[cnt]=w2;
    to[cnt]=v;
    nxt[cnt]=first[u];
    first[u]=cnt;
}

int dep[100010];

bool bfs() {
    memset(dep,0,sizeof(dep));
    queue<int>q;
    q.push(1);
    dep[s]=1;
    while(!q.empty()) {
        int e;
        int head=q.front();
        q.pop();
        for(e=first[head];e;e=nxt[e]) {
            int v=to[e];
            if(dep[v]==0&&w[e]>0) {
                dep[v]=dep[head]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=0;
}

int dinic(int now,int flow) {
    if(now==t) {
        return flow;
    }
    int out=0;
    for(int e=first[now];e&&flow;e=nxt[e]) {
        int v=to[now];
        if(dep[v]!=dep[now]+1) continue;
        if(!w[e]) continue;
        int outnow=dinic(v,min(w[e],out));
        flow-=outnow;
        w[e]-=outnow;
        w[e^1]+=outnow;
        out+=outnow;
    }
    if(out==0) dep[now]=0;
    return out;
}

int main() {
    int ans=0;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) {
        int u2,v2,w2;
        cin>>u2>>v2>>w2;
        add(u2,v2,w2);
        add(v2,u2,0);
    }
    while(bfs()) {
        ans+=dinic(s,1e9+114514);
    }
    cout<<ans;
}

by AK_Dream @ 2020-06-27 10:25:36

上面不都说了吗。。。cnt初值赋为1 不然你那个w[e^1]找到的不是反向边

by optimize_2 @ 2020-06-27 10:30:08

@LK_Luogu 改过了，还是超时

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

int n,m,s,t,cnt=1,first[10010],nxt[200010],to[200010],w[200010];
bool vst[100010];

void add(int u,int v,int w2) {
    cnt++;
    w[cnt]=w2;
    to[cnt]=v;
    nxt[cnt]=first[u];
    first[u]=cnt;
}

int dep[10010];

bool bfs() {
    memset(dep,0,sizeof(dep));
    queue<int>q;
    q.push(1);
    dep[s]=1;
    while(!q.empty()) {
        int head=q.front();
        q.pop();
        for(int e=first[head];e;e=nxt[e]) {
            int v=to[e];
            if(!dep[v]&&w[e]) {
                dep[v]=dep[head]+1;
                q.push(v);
            }
        }
    }
    return dep[t];
}

int dinic(int now,int flow) {
    if(now==t) {
        return flow;
    }
    int out=0;
    for(int e=first[now];e&&flow;e=nxt[e]) {
        int v=to[e];
        if((dep[v]==dep[now]+1)&&(w[e])) {
            int outnow=dinic(v,min(w[e],flow));
            flow-=outnow;
            w[e]-=outnow;
            w[e^1]+=outnow;
            out+=outnow;
        }
    }
    if(out==0) dep[now]=0;
    return out;
}

int main() {
    int ans=0;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) {
        int u2,v2,w2;
        cin>>u2>>v2>>w2;
        add(u2,v2,w2);
        add(v2,u2,0);
    }
    while(bfs()) {
        ans+=dinic(s,2e9);
    }
    cout<<ans;
}