欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

费用流

程序员文章站 2022-05-22 14:57:32
...
const int inf = 0x3f3f3f3f;
struct mcmf{
    int he[maxn],tot,edge[maxm],ne[maxm],ver[maxm],cost[maxm];
    int pre[maxn],d[maxn];
    bool vis[maxn];
    int n;
    void init(int x){
        n = x;
        tot = 1;
        for( int i = 0;i <= n;i++ ) he[i] = 0;
    }
    void add(int x,int y,int cap,int c){
        ver[++tot] = y;
        ne[tot] = he[x];
        he[x] = tot;
        edge[tot] = cap;
        cost[tot] = c;
        ver[++tot] = x;
        ne[tot] = he[y];
        he[y] = tot;
        edge[tot] = 0;
        cost[tot] = -c;
    }
    bool spfa(int s,int t){
        queue<int>q;
        for(int i = 0;i < n;i++){
            d[i] = inf;
            vis[i] = false;
            pre[i] = -1;
        }
        d[s] = 0;
        vis[s] = true;
        q.push(s);
        while(!q.empty()){
            int x = q.front();
            q.pop();
            vis[x] = false;
            for(int cure = he[x]; cure ;cure = ne[cure]){
                int y = ver[cure];
                if(edge[cure] && d[y] > d[x] + cost[cure] ){
                    d[y] = d[x] + cost[cure];
                    pre[y] = cure;
                    if(!vis[y]){
                        vis[y] = true;
                        q.push(y);
                    }
                }
            }
        }
        if(pre[t] == -1)return false;
        else return true;
    }

    int mincost(int s,int t,int &cc){
        int flow = 0;
        cc = 0;
        while(spfa(s,t)){
            int mn = inf;
            for(int cure = pre[t];cure != -1;cure = pre[ ver[cure^1] ]){
                if(mn > edge[cure])
                    mn = edge[cure];
            }
            for(int cure = pre[t];cure != -1;cure = pre[ ver[cure^1] ]){
                edge[cure] -= mn;
                edge[cure^1] += mn;
                cc += cost[cure] * mn;
            }
            flow += mn;
        }
        return flow;
    }
} g;