「网络流 24 题」分配问题

「网络流 24 题」分配问题
题解:一个最大费用最大流的模板题,只要将最小费用最大流的费用建图中的权值反过来建图,

#include <bits/stdc++.h>

const int MAXN = 5000000,INF = 10000000;

using namespace std;

int n,s,t,e1 = 2,e2 = 2;
int head1[MAXN],head2[MAXN],pri[MAXN],dis[MAXN];
bool inq[MAXN];

struct node{
    int u,v,w,c,f,next;
}edge1[MAXN],edge2[MAXN];

inline void addedge1(int u,int v,int w,int c){
    edge1[e1] = (node){u,v, w,c,0,head1[u]};head1[u] = e1++;
    edge1[e1] = (node){v,u,-w,0,0,head1[v]};head1[v] = e1++;
}

inline void addedge2(int u,int v,int w,int c){
    edge2[e2] = (node){u,v, w,c,0,head2[u]};head2[u] = e2++;
    edge2[e2] = (node){v,u,-w,0,0,head2[v]};head2[v] = e2++;
}

inline void init(){
    scanf("%d",&n);
    int v;s = 0;t = 2*n+1;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++){
            scanf("%d",&v);
            addedge1(i,j+n, v,1);
            addedge2(i,j+n,-v,1);
        }
    for(int i = 1;i <= n;i++) {
        addedge1(s,i,0,1);
        addedge1(i+n,t,0,1);
        addedge2(s,i,0,1);
        addedge2(i+n,t,0,1);
    }
}
queue<int>Q;
inline bool spfa1(){
    for(int i = s;i <= t;i++) {
        inq[i] = false;
        dis[i] = INF;
        pri[i] = 0;    
    }
    Q.push(s);inq[s] = true;dis[s] = 0;
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head1[x];i;i = edge1[i].next){
            node E = edge1[i];
            if(dis[E.v] > dis[x] + E.w && E.c > E.f){
                dis[E.v] = dis[x] + E.w;
                pri[E.v] = i; 
                if(!inq[E.v]){
                    Q.push(E.v);
                    inq[E.v] = false;
                } 
            }
        }
    }
    return pri[t] ? true : false; 
}

inline int MCMF1(){
    int tmp,cost = 0,flow = 0;
    while(spfa1()){
        tmp = INF;
        for(int i = pri[t];i;i = pri[edge1[i^1].v])
            tmp = min(tmp,edge1[i].c-edge1[i].f);
        for(int i = pri[t];i;i = pri[edge1[i^1].v]){
            edge1[i].f += tmp;
            edge1[i^1].f -= tmp;
            cost += tmp*edge1[i].w;
         }
         flow += tmp;
    }
    return cost;
}

inline bool spfa2(){
    for(int i = s;i <= t;i++) {
        inq[i] = false;
        dis[i] = INF;
        pri[i] = 0;    
    }
    Q.push(s);inq[s] = true;dis[s] = 0;
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head2[x];i;i = edge2[i].next){
            node E = edge2[i];
            if(dis[E.v] > dis[x] + E.w && E.c > E.f){
                dis[E.v] = dis[x] + E.w;
                pri[E.v] = i; 
                if(!inq[E.v]){
                    Q.push(E.v);
                    inq[E.v] = false;
                } 
            }
        }
    }
    return pri[t] ? true : false; 
}

inline int MCMF2(){
    int tmp,cost = 0,flow = 0;
    while(spfa2()){
        tmp = INF;
        for(int i = pri[t];i;i = pri[edge2[i^1].v])
            tmp = min(tmp,edge2[i].c-edge2[i].f);
        for(int i = pri[t];i;i = pri[edge2[i^1].v]){
            edge2[i].f += tmp;
            edge2[i^1].f -= tmp;
            cost += tmp*edge2[i].w;
         }
         flow += tmp;
    }
    return cost;
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();
    printf("%d\n",MCMF1());
    printf("%d\n",-MCMF2());
    return 0;
} 
Last modification:October 25th, 2018 at 02:53 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment