[网络流24题] 运输问题

题意

题解

这题..和分配问题不是同一道题吗...
同样的建图方式直接跑最小费用最大流即可。
将边权变负再跑一遍取负得最大费用。
详细题解见 https://blog.nowcoder.net/n/9a823354bd454d0aa33fcbac1c2fb831

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 200 + 10;
const int mod = 1e9 + 7;

struct Edge{
    int to, cap, cost;
    int nxt;
}edges[maxn * maxn];

int head[maxn],tot;
int vis[maxn],pre[maxn],dis[maxn];

void addedge(int u,int v,int f,int c)
{
    edges[tot] = {v,f,c,head[u]};
    head[u] = tot++;
}

void addedges(int u,int v,int f,int c)
{
    addedge(u,v,f,c);
    addedge(v,u,0,-c);
}

bool spfa(int s,int t)
{
    memset(pre,-1,sizeof(pre));
    fill(dis,dis+maxn,inf);
    memset(vis,0,sizeof(vis));
    queue<int> q;
    vis[s] = 1;
    dis[s] = 0;
    q.push(s);
    while(q.size()){
        int hd = q.front();
        q.pop();
        vis[hd] = 0;
        for(int i = head[hd];~i;i = edges[i].nxt){
            auto &e = edges[i];
            if(e.cap > 0 && dis[e.to] > dis[hd] + e.cost){
                dis[e.to] = dis[hd] + e.cost;
                pre[e.to] = i;
                if(!vis[e.to]){
                    vis[e.to] = 1;
                    q.push(e.to);
                }
            }
        }
    }
    return ~pre[t];
}

int mcmf(int s,int t){
    int flow = 0;
    int cost = 0;
    while(spfa(s,t)){
        int mf= inf;
        for(int i = pre[t];~i;i = pre[edges[i^1].to]){
            mf = min(mf,edges[i].cap);
        }
        flow += mf;
        for(int i = pre[t];~i;i = pre[edges[i^1].to]){
            edges[i].cap -= mf;
            edges[i^1].cap += mf;
            cost += mf * edges[i].cost;
        }
    }
    return cost;
}

int a[maxn];
int b[maxn];
int g[maxn][maxn];

int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
    int s = 0,t = maxn - 1;
    tot = 0;
    memset(head,-1,sizeof(head));
    int m,n;
    cin>>m>>n;
    for(int i = 1;i <= m;++i){
        cin>>a[i];
        addedges(s,i,a[i],0);
    }
    for(int i = 1;i <= n;++i){
        cin>>b[i];
        addedges(i+m,t,b[i],0);
    }
    for(int i = 1;i <= m;++i){
        for(int j = 1;j <= n;++j){
            cin>>g[i][j];
            addedges(i,j+m,inf,g[i][j]);
        }
    }
    int mi = mcmf(s,t);
    tot = 0;
    memset(head,-1,sizeof(head)); 
    for(int i = 1;i <= m;++i){
        addedges(s,i,a[i],0);
    }
    for(int i = 1;i <= n;++i){
        addedges(i+m,t,b[i],0);
    }
    for(int i = 1;i <= m;++i){
        for(int j = 1;j <= n;++j){
            addedges(i,j+m,inf,-g[i][j]);
        }
    }
    int mx = -mcmf(s,t);
    printf("%d\n%d\n",mi,mx);
   return 0;
}