Chlience

【算法】网络流模板
网络流 & 最小费用最大流模板网络流这是一份加了奇奇怪怪优化的不知道什么鬼的网络流模板其实就是 $ISAP$ 而已...
扫描右侧二维码阅读全文
26
2018/12

【算法】网络流模板

网络流 & 最小费用最大流模板

网络流

这是一份加了奇奇怪怪优化的不知道什么鬼的网络流模板

其实就是 $ISAP$ 而已啦
听说雅礼大佬 $2011$ 年写出了这个奇短的 $ISAP$,Orz

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 10010;
const int M = 200010;
struct edge {int t , n , flow;}e[M << 1];
int cur[N] , head[N] , tot = 1;
int f[N] , d[N];
int n , m , s , t;
void addedge(int u , int v , int flow) {
    ++ tot;
    e[tot].t = v;
    e[tot].flow = flow;
    e[tot].n = head[u];
    head[u] = tot;
}
int dfs(int now , int flow) {
    if(now == t) return flow;
    int use = 0;
    for(int i = cur[now] ; i ; i = e[i].n) {
        cur[now] = i;
        if(e[i].flow && d[e[i].t] + 1 == d[now]) {
            int tmp = dfs(e[i].t , min(flow - use , e[i].flow));
            use += tmp;
            e[i].flow -= tmp;
            e[i ^ 1].flow += tmp;
            if(flow == use) return use;
        }
    }
    cur[now] = head[now];
    if(!(--f[d[now]]))
        d[s] = n;
    ++ f[++ d[now]];
    return use;
}
int main() {
    n = read(); m = read();
    s = read(); t = read();
    for(int i = 1 ; i <= m ; ++ i) {
        int u = read() , v = read() , flow = read();
        addedge(u , v , flow);
        addedge(v , u , 0);
    }
    f[0] = n;
    int ans = 0;
    while(d[s] < n) ans += dfs(s , 1 << 30);
    printf("%d\n" , ans);
    return 0;
}

最小费用最大流

同样的,最小费用最大流我也用 $ISAP$ 跑了

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 5010;
const int M = 100010;
const int MAX = 2139062143;
struct edge {
    int t , n , flow , dist;
    void add(int _t , int _n , int _flow , int _dist) {t = _t; n = _n; flow = _flow; dist = _dist;}
}e[M];
int head[N] , tot = 1 , cur[N];
int n , m , s , t;
int f[N] , d[N] , dis[N];
bool vis[N];
queue <int> q;
void addedge(int u , int v , int flow , int dist) {
    e[++ tot].add(v , head[u] , flow , dist);
    head[u] = tot;
    e[++ tot].add(u , head[v] , 0 , - dist);
    head[v] = tot;
}
bool spfa() {
    memset(dis , 127 , sizeof(dis));
    dis[t] = 0; vis[t] = 1;
    q.push(t);
    while(!q.empty()) {
        int now = q.front(); q.pop(); vis[now] = 0;
        for(int i = head[now] ; i ; i = e[i].n) {
            if(e[i ^ 1].flow > 0 && dis[now] + e[i ^ 1].dist < dis[e[i].t]) {
                dis[e[i].t] = dis[now] + e[i ^ 1].dist;
                if(!vis[e[i].t]) q.push(e[i].t);
                vis[e[i].t] = 1;
            }
        }
    }
    if(dis[s] == MAX) return false;
    return true;
}
int dfs(int now , int flow) {
    if(now == t) return flow;
    int use = 0;
    for(int i = cur[now] ; i ; i = e[i].n) {
        cur[now] = i;
        if(dis[now] != dis[e[i].t] + e[i].dist) continue;
        if(e[i].flow && d[e[i].t] + 1 == d[now]) {
            int tmp = dfs(e[i].t , min(e[i].flow , flow - use));
            use += tmp;
            e[i].flow -= tmp;
            e[i ^ 1].flow += tmp;
            if(flow == use) return use;
        }
    }
    cur[now] = head[now];
    if(!-- f[d[now]])
        d[s] = n;
    ++ f[++ d[now]];
    return use;
}
void MCMF() {
    int dist = 0 , flow = 0;
    while(spfa()) {
        memset(cur , 0 , sizeof(cur));
        memset(f , 0 , sizeof(f));
        memset(d , 0 , sizeof(d));
        f[0] = n;
        int ans = 0;
        while(d[s] < n)
            ans += dfs(s , 1 << 30);
        flow += ans;
        dist += ans * dis[s];
    }
    printf("%d %d\n" , flow , dist);
}
int main() {
    n = read(); m = read();
    s = read(); t = read();
    for(int i = 1 ; i <= m ; ++ i) {
        int u = read() , v = read() , flow = read() , dist = read();
        addedge(u , v , flow , dist);
    }
    MCMF();
    return 0;
}
Last modification:December 26th, 2018 at 09:01 pm

Leave a Comment