程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Acdream 1171 Matrix sum 上下界費用流

Acdream 1171 Matrix sum 上下界費用流

編輯：C++入門知識

Acdream 1171 Matrix sum 上下界費用流

題目鏈接：點擊打開鏈接

Matrix sum

Time Limit: 8000/4000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others) SubmitStatisticNext Problem

Problem Description

sweet和zero在玩矩陣游戲，sweet畫了一個N * M的矩陣，矩陣的每個格子有一個整數。zero給出N個數Ki，和M個數Kj，zero要求sweet選出一些數，滿足從第 i 行至少選出了Ki個數，第j列至少選出了Kj個數。這些數之和就是sweet要付給zero的糖果數。sweet想知道他至少要給zero多少個糖果，您能幫他做出一個最優策略嗎？

Input

首行一個數T(T <= 40)，代表數據總數，接下來有T組數據。

每組數據：

第一行兩個數N,M(1 <= N,M <= 50)

接下來N行，每行M個數（范圍是0-10000的整數)

接下來一行有N個數Ki,表示第i行至少選Ki個元素(0 <= Ki <= M)

最後一行有M個數Kj，表示第j列至少選Kj個元素(0 <= Kj <= N)

Output

每組數據輸出一行，sweet要付給zero的糖果數最少是多少

Sample Input

Sample Output

n行作為左端點 m作為右端點建一個二部圖

n個點連到源點流量為inf ，費用為0

m個點連到匯點流量為inf 費用為0

n個點和m個點之間連一條費用為 mp[i][j] ，流量為1的點

--------------------------- 以上是普通建圖-----------------------

為了達到有下界的效果

給下界對應的點加一個費用為-inf，流量為ki的邊，這樣讓費用流強制把所有費用為-inf的邊先跑

意思也就是先使得下界的邊滿流。

當費用>0時，說明這次跑的邊中不存在有下界的邊，那麼就相當於下界的邊已經滿流，所以直接終止費用流

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
#define ll int
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define N 105
#define M 1005
struct Edge
{
    ll from,to,cap,cost,nex;
    Edge(){}
    Edge(ll from,ll to,ll cap,ll cost,ll next):from(from),to(to),cap(cap),cost(cost),nex(next){}
}edges[M<<1];
ll head[N], edgenum;
ll d[N], a[N], p[N];
bool inq[N];
void add(ll from,ll to,ll cap,ll cost)
{
    edges[edgenum] = Edge(from,to,cap,cost,head[from]);
    head[from] = edgenum++;
    edges[edgenum] = Edge(to,from,0,-cost,head[to]);
    head[to] = edgenum++;
}
bool spfa(ll s, ll t, ll &flow, ll &cost)
{
    for(ll i = 0; i <= t; i++) d[i] = inf;
    memset(inq, 0, sizeof inq);
    queueq;
    q.push(s);
    d[s] = 0; a[s] = inf;
    while(!q.empty())
    {
        ll u = q.front(); q.pop();
        inq[u] = 0;
        for(ll i = head[u]; ~i; i = edges[i].nex)
        {
            Edge &e = edges[i];
            if(e.cap && d[e.to] > d[u] + e.cost)
            {
                d[e.to] = d[u] + e.cost;
                p[e.to] = i;
                a[e.to] = min(a[u], e.cap);
                if(!inq[e.to])
                {inq[e.to]=1; q.push(e.to);}
            }
        }
    }
    if(d[t]>0) return false;
    cost += d[t] * a[t];
    flow += a[t];
    ll u = t;
    while(u != s){
        edges[ p[u] ].cap -= a[t];
        edges[p[u]^1].cap += a[t];
        u = edges[p[u]^1].to;
    }
    return true;
}
ll Mincost(ll s,ll t){//返回最小費用
    ll flow = 0, cost = 0;
    while(spfa(s, t, flow, cost));
    return cost;
}
void init(){memset(head,-1,sizeof head); edgenum = 0;}
 
int n,m;
int mp[55][55];
int h[55], l[55];
void input(){
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        scanf("%d",&mp[i][j]);
    for(int i = 1; i <= n; i++)scanf("%d",&h[i]);
    for(int i = 1; i <= m; i++)scanf("%d",&l[i]);
}
#define hehe 100000
int main(){
    int T, i, j;scanf("%d",&T);
    while(T--){
        input();
        init();
        int from = 0, to = n+m+1;
        int les = 0;
        for(i = 1; i <= n; i++)
        {
            les += h[i];
            add(from, i, h[i], -hehe);
            add(from, i, inf, 0);
        }
        for(i = 1; i <= m; i++)
        {
            les += l[i];
            add(n + i, to, l[i], -hehe);
            add(n + i, to, inf, 0);
        }
        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
                add(i, n+j, 1, mp[i][j]);
        printf("%d\n", Mincost(from, to) + hehe*les);
    }
    return 0;
}
/*
http://acdream.info/onecontest/1080#problem-H
http://paste.ubuntu.com/7930356/#userconsent#
 
*/