题：http://acm.hdu.edu.cn/showproblem.php?pid=6126
题意：题目给出n，m，k
然后给出n*m的矩阵a[i][j]代表第i个人在获得j 颗糖果能得到的满足值；
k行[x,y,z]表示第x个人的糖果减去第y个人的糖果需要不大于z。
分析：
因为题目的z可能为负数，而网络流建边容量时的负数概念不能被覆盖，所有建立一个等效‘0’位置的值，sign=1000（大于负数绝对值就行）
对于每个人，我们把他拆成m个点，源点向第一个点连inf流量的边，而剩余的点连sign-a[][]中存的值，最后一个a[][]则连被分出来的点到超级汇点；
先不考虑限制条件，我们现在建边所跑出来的最大流并非每个人的最小满足值之和，因为我们建容量时sign-a[][]；而n*sign-maxflow则是每个人的最大满足值之和
而题目又有限制条件，所有把满足的按容量inf连，具体看代码，得到答案就是我们上面说的那个
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #define mem0(a) memset(a,0,sizeof(a)) #define meminf(a) memset(a,0x3f,sizeof(a)) using namespace std; typedef long long ll; typedef long double ld; typedef double db; const int maxn=55,maxk=100005,inf=0x3f3f3f3f; int a[maxn][maxn]; int head[maxn*maxn],dist[maxn*maxn],current[maxn*maxn]; int num; struct Edge { int from,to,flow,pre; }; Edge edge[maxk]; void addedge(int from,int to,int flow) { edge[num]=(Edge){from,to,flow,head[from]}; head[from]=num++; edge[num]=(Edge){to,from,0,head[to]}; head[to]=num++; } bool bfs (int n) { queue<int> q; q.push(0); memset(dist,-1,sizeof(dist)); dist[0]=0; while (!q.empty()) { int now=q.front(); q.pop(); for (int i=head[now];i!=-1;i=edge[i].pre) { int to=edge[i].to; if (dist[to]==-1&&edge[i].flow>0) { dist[to]=dist[now]+1; q.push(to); } } } return dist[n]!=-1; } int dfs(int now,int flow,int n) { int f; if (now==n) return flow; for (int i=current[now];i!=-1;i=edge[i].pre) { int to=edge[i].to; current[now]=i; if (dist[now]+1==dist[to]&&edge[i].flow>0&& (f=dfs(to,min(flow,edge[i].flow),n))) { edge[i].flow-=f; edge[i^1].flow+=f; return f; } } return 0; } int dinic(int n) { int sum=0,f; while (bfs(n)) { memcpy(current,head,sizeof(head)); while (f=dfs(0,inf,n)) sum+=f; } return sum; } int main() { int cas; scanf("%d",&cas); while (cas--) { int n,m,k,i,j,x,y,z; memset(head,-1,sizeof(head)); num=0; scanf("%d%d%d",&n,&m,&k); for (i=1;i<=n;i++) { scanf("%d",&a[i][1]); addedge(0,(i-1)*m+1,1e7); for (j=2;j<=m;j++) { scanf("%d",&a[i][j]); addedge((i-1)*m+j-1,(i-1)*m+j,1000-a[i][j-1]); } addedge(i*m,n*m+1,1000-a[i][m]); } for (i=1;i<=k;i++) { scanf("%d%d%d",&x,&y,&z); for (j=max(z+1,1);j<=m&&j-z<=m;j++) { addedge((x-1)*m+j,(y-1)*m+j-z,1e7); } if (j-z>m&&j<=m) addedge((x-1)*m+j,n*m+1,1e7); } int ans=dinic(n*m+1); if (ans>1e7) printf("-1 "); else printf("%d ",n*1000-ans); } return 0; }