萌新求助网络流板子

RT

dinic + 当前弧优化

又 WA 又 T

就差没把蓝书给扫描进电脑里去了

评测记录

#include <bits/stdc++.h>

namespace Basic {
    template <typename Temp> inline void read(Temp & res) {
        Temp fh = 1; res = 0; char ch = getchar();
        for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
        for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
        res = res * fh; 
    }
    template <typename Temp> inline void Checkmax(Temp & res, Temp comp)  {if(comp > res) res = comp;} 
    template <typename Temp> inline void Checkmin(Temp & res, Temp comp)  {if(comp < res) res = comp;}
}

using namespace std;
using namespace Basic;

const int Maxn = 2e2 + 5;
const int Maxm = 5e3 + 5;
const int INF = 0x7fffffff >> 1;

struct e {
    int to, nxt, flow;
} b[Maxm << 1];
int head[Maxn], ecnt;

inline void add(int u, int v, int f) {b[++ecnt] = (e){v, head[u], f}; head[u] = ecnt;}

int depth[Maxn], curr[Maxn];

int n, m, st, ed;

int Max_flow, last_flow;

queue<int> q;
inline bool bfs() {
    memset(depth, 0, sizeof(depth));
    while(!q.empty()) q.pop();
    depth[st] = 1; q.push(st); curr[st] = head[st];
    while(!q.empty()) {
        int tnow = q.front(); q.pop();
        for(register int i = head[tnow]; i; i = b[i].nxt) {
            int tto = b[i].to, tw = b[i].flow;
            if((!tw) || (depth[tto])) continue;
            q.push(tto);
            depth[tto] = depth[tnow] + 1; curr[tto] = head[tto];
            if(tto == ed) return true;
        }
    }
    return false;
}

int dfs(int t, int Flow) {
    if(t == ed) return Flow;
    int rest = Flow, k, i;
    for(i = curr[t]; i && rest; i = b[i].nxt) {
        int tto = b[i].to, tw = b[i].flow;
        if((tw == 0) || (depth[tto] != depth[t] + 1)) continue;
        k = dfs(tto, min(rest, tw));
        rest -= k;
        b[i].flow -= k;
        b[i ^ 1].flow += k;
        if(!k) depth[tto] == 0;
    }
    curr[t] = i;
    return Flow - rest;
}

int main() {
    read(n); read(m); read(st); read(ed);
    int x, y, z;
    while(m--) {
        read(x); read(y); read(z);
        add(x, y, z);
        add(y, x, 0);
    }
    while(bfs()) {
        /*
        for(register int i = 1; i <= n; ++i) {
            printf("%d ", depth[i]); 
        }
        puts("");
        */
        while(last_flow = dfs(st, INF)) Max_flow += last_flow;
    }
    printf("%d", Max_flow);
    return 0;
}