Acdream 1171 Matrix sum 上下界费用流 - c++编程基础

TOP

Acdream 1171 Matrix sum 上下界费用流

2015-07-20 18:00:50 来源: 作者: 【大中小】浏览:2次

题目链接：点击打开链接

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); queue
             
              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# */


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++ string实现原理	下一篇：Codeforces Round #246 (Div. 2) ..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: