HDOJ 3549 Flow Problem --- Dinic算法模板

柔光的暖阳◎ 2023-06-24 08:09 16阅读 0赞

> 题解：最大流问题，套dinic模板即可

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    const int INF = 1e9;
    
    int n,m;
    int dis[3000];
    struct Edge {
        int to, nxt, c;
    } e[3000];
    int head[3000];
    int cnt = 0;
    
    void add(int a, int b, int c) {
        cnt++;
        e[cnt].to = b;
        e[cnt].c = c;
        e[cnt].nxt = head[a];
        head[a] = cnt;
    }
    
    void init() {
        cnt = -1;
        memset(head, - 1, sizeof(head));
    }
    
    bool bfs(int st, int ed) {
        queue<int> q;
        memset(dis, -1, sizeof(dis));
        dis[st] = 0;
        q.push(st);
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            for(int i = head[x]; i != -1; i = e[i].nxt) {
                int now = e[i].to;
                if(dis[now] == -1 && e[i].c) {
                    dis[now] = dis[x] + 1;
                    q.push(now);
                }
            }
        }
        return dis[ed] != -1;
    }
    
    int dfs(int st,int ed, int maxflow) {
        if(st == ed) {
            return maxflow;
        }
        int ans = 0;
        for (int i = head[st]; i!=-1; i = e[i].nxt) {
            int now = e[i].to;
            if(dis[now]!=dis[st]+1 || e[i].c==0 || maxflow <= ans) continue;
            int f = dfs(now, ed, min(e[i].c, maxflow-ans));
            e[i].c -= f;
    e[i^1].c += f; 
            ans += f;
        }
      //  if(!ans) dis[st] = -1;
        return ans;
    }
    
    int Dinic(int st, int ed) {
        int ans = 0;
        while(bfs(st, ed)) {
            int k = 0;
            k = dfs(st, ed, INF);
                ans += k;
        }
        return ans;
    }
    
    int main() {
        int t;
        scanf("%d",&t);
        for(int i = 1;i <= t;i++) {
            init();
            scanf("%d%d", &n,&m);
            while(m--) {
                int u,v,t;
                scanf("%d%d%d",&u,&v,&t);
                add(u,v,t);
    add(v,u,0);
            }
            printf("Case %d: %d\n", i, Dinic(1,n));
        }
    
        return 0;
    }