首页 > 代码库 > Acdream 1171 Matrix sum 上下界费用流

Acdream 1171 Matrix sum 上下界费用流

2024-07-15 12:16:22   225人阅读

题目链接：点击打开链接

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

1
4 4
1 1 1 1
1 10 10 10
1 10 10 10
1 10 10 10
1 1 1 1
1 1 1 1

Sample Output

6

n行作为左端点 m作为右端点建一个二部图

n个点连到源点 流量为inf ，费用为0

m个点连到汇点 流量为inf 费用为0 

n个点和m个点之间连一条费用为 mp[i][j] ，流量为1的点

--------------------------- 以上是普通建图-----------------------

为了达到有下界的效果

给下界对应的点加一个费用为-inf，流量为ki的边，这样让费用流强制把所有费用为-inf的边先跑

意思也就是先使得下界的边满流。

当费用>0时， 说明这次跑的边中不存在有下界的边，那么就相当于下界的边已经满流，所以直接终止费用流


#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
#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);
    queue<ll>q;
    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#
 
*/


联系
我们