Give out candies 最小割

Give out candies

问题描述

There are n children numbered 1 to n, and HazelFan’s task is to give out candies to the children. Each children must be given at least 1 and at most m candies. The children raised k pieces of requirements, and every piece includes three integers x,y,z, means that the number of candies given to the child numbered x, subtract the number of candies given to the child number y, the result should not be more than z. Besides, if the child numbered i is given j candies, he or she will get wi,j satisfaction score, now you need to help HazelFan maximize the sum of the satisfaction scores of these children.( 0 < wi,j <=1000 )

输入格式

The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
For each test case:
The first line contain three positive integers n,m,k(1≤n,m≤50,1≤k≤150).
The next n lines, the ith line contains m positive integers, the jth integer denotes wi,j.
The next k lines, each line contains three integers x,y,z(1≤x,y≤n,∣z∣<233), denoting a piece of requirement.

输出格式

For each test case:
A single line contains a nonnegative integer, denoting the answer. Particularly, if there is no way to give out candies, print -1.

样例输入

2
2 1 1
1
1
1 2 1
3 3 2
1 2 3
2 3 1
3 1 2
1 2 0
2 3 0

样例输出

2
7

---

题意：
n个孩子，每个孩子要分到至少1个，至多m个糖果。第i个孩子分到j个糖果会对答案有wi,j的贡献。在满足形如“x y z”，即第x个孩子的糖果不能比第y个孩子的糖果多z个以上的k个限制下，求答案的最大值。

---

题解：
观察到数据范围非常小，考虑爆搜网络流。

根据数据范围，不难想到把每个孩子拆成m个点。只不过(i,j)不是表示i号孩子恰得到了j颗糖，而是i号孩子至少得到了j颗糖。

为什么这么定义？因为这样才能向最小割模型转化。不考虑限制的情况下，先这样建图：

用(i,j)表示i号孩子至少得到j颗糖。
对于任意0 < j < m，连接(i,j)和(i,j+1),容量为-wi,j。
连接源点和(i,1)，容量为inf。
连接(i,m)和汇点,容量为-wi,m。

直观点就是这个样子：

容易看出，在没有限制的条件下，上图的最小割的相反数就是答案最大值。与S在一个集合里的点，其代表的条件是被满足的。这就解释了(i,j)为什么这样定义。

由于网络流算法不允许容量为负，那么有一个经典的处理方法：将每条边加上一个相等的足够大的数将边权全部转为非负，这样不会影响割边的选取。由于本题中wi,j最大为1000，因此对上述的每条边容量加上1000，答案就用1000*n减去最小割即可。

没有限制的条件下这样的做法是很智障的，现在考虑加上限制后怎么做。本题中有一个比较巧妙的建图方式。考虑下面的图：

上图有一个性质：
考虑最小割。在正常情况下，割掉了蓝边之后，在S->a->T的这一支上就一定不会割掉绿色部分的边。原因很简单：如果割掉绿色部分的边，那么a就在T集合中，而因为b在S集合中，因此b到a的边会被割掉。这条边的容量是inf，这样一定不是最小割。

那么不正常的情况是什么？当然是无解的情况，即用最小割算法都会割掉inf边的情况。

当然你也可以用差分约束系统判无解。

套用到本题上，就是对于一个约束”x y z”，将(x,j)连一条到(y,j-z)，容量为inf的边。如果下标越界，相应地连向源点或汇点。其余部分按照之前的方式建图即可。

---

代码：

#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 5000
#define MAXM 50000
using namespace std;

int N,M,K,Ans,w[55][55],id[55][55];

int nex[MAXM],en[MAXM],G[MAXM],las[MAXN],st[MAXN],tot;
void Add(int x,int y,int g){
    en[++tot]=y;
    nex[tot]=las[x];
    las[x]=st[x]=tot;
    G[tot]=g;
}
void Link(int x,int y,int g){
    Add(x,y,g);Add(y,x,0);
}

int dis[MAXN],Cnt[MAXN],S,P,T;
int SAP(int x,int flow){
    if(x==T)return flow;
    int i,y,d=0,tmp;
    for(i=st[x];i;i=nex[i]){
        y=en[i];
        if(G[i]&&dis[x]==dis[y]+1){
            tmp=SAP(y,min(flow-d,G[i]));
            d+=tmp;G[i]-=tmp;G[i^1]+=tmp;
            st[x]=i;
            if(d==flow||dis[S]>=P)return d;
        }
    }
    st[x]=las[x];
    if(--Cnt[dis[x]]==0)dis[S]=P;
    Cnt[++dis[x]]++;
    return d;
}


void Clear(){
    tot=1;memset(las,0,sizeof(las));
    memset(Cnt,0,sizeof(Cnt));
    memset(dis,0,sizeof(dis));
}

int main(){
int Q,i,j,k,x,y,z;scanf("%d",&Q);
while(Q--){
    Clear();
    scanf("%d%d%d",&N,&M,&K);
    for(i=1,k=0;i<=N;i++)
    for(j=1;j<=M;j++)scanf("%d",&w[i][j]),id[i][j]=++k;

    S=k+1;T=P=S+1;

    for(i=1;i<=N;i++)
    for(j=1;j<M;j++)Link(id[i][j],id[i][j+1],1000-w[i][j]);
    for(i=1;i<=N;i++)Link(id[i][M],T,1000-w[i][M]),Link(S,id[i][1],1e9);

    for(i=1;i<=K;i++){
        scanf("%d%d%d",&x,&y,&z);
        for(j=1;j<=M;j++){
            if(j-z<=0)Link(id[x][j],S,1e9);
            else if(j-z>M)Link(id[x][j],T,1e9);
            else Link(id[x][j],id[y][j-z],1e9);
        }
    }

    Ans=N*1000;
    while(dis[S]<=P)Ans-=SAP(S,1e9);
    if(Ans<0)puts("-1");
    else printf("%d\n",Ans);
}
}