hdu 6126 Give out candies(最小割)
题意：
有(n)个小朋友，标号为(1)到(n)，你要给每个小朋友至少(1)个且至多(m)个的糖果。小朋友们共提出(k)个要求，每个要求包括三个整数(x,y,z)，表示(x)号小朋友得到的糖果数减去(y)号小朋友得到的糖果数，结果应当不大于(z)。如果你给(i)号小朋友(j)颗糖果，他会获得(w_{i,j})
的满意度，你需要最大化所有小朋友的满意度之和。(1leq n,mleq50,1leq kleq150,1leq w_{i,j}leq10^3)
。
题解：
用(i.j)这点表示给第(i)个孩子至少(j)块糖，当这个点属于S集合时所代表条件成立。然后(i.j->i.j+1)连(1000-w_{i,j}，i.m)向(T)连(1000-w_{i,m}，S)向(i.1)连(inf)。如果存在(a_x-a_y>=z)，(x.k->y.k+z)连(inf)。跑最小割，再用(n*1000)减掉答案。
网络流的题目建模总是很玄的，结合这篇博客理解了一下，虽然还是没有完全领悟。
首先考虑没有限制的情况，那么显然选(w_{i,j})越大越好，按题解建图的方法,令这条边的容量为(F-w_{i,j})，F为一个足够大的数,显然最小割会选到这条边。
想象一下 对限制连流量无穷大的边的情况
首先在合法情况下，给一条边的容量设置为无穷大,表示这条边是无法被最小割选到的
如果没有限制，每个人选择方案可以在同侧，连了限制的边后，就限制了选择方案必须在这条边的两侧，这样才能保证能够割到这条无穷大的边，如果跑出来的流量是无穷大的，说明最小割不存在，没有合法选择。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3000;
const int inf = 0x3f3f3f3f;
struct Edge{
int u,v,cap,flow;
Edge(){};
Edge(int u,int v,int cap,int flow):u(u),v(v),cap(cap),flow(flow){}
};
struct Dinic{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
int vis[maxn],d[maxn],cur[maxn];
void init(int n){
this->n = n;
for(int i = 0;i < n;i++) G[i].clear();
edges.clear();
}
void add(int u,int v,int cap){
edges.push_back(Edge(u,v,cap,0));
edges.push_back(Edge(v,u,0,0));
m = edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool bfs(){
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(s);vis[s] = 1,d[s] = 0;
while(!q.empty()){
int u = q.front();q.pop();
for(auto x:G[u]){
auto e = edges[x];
if(!vis[e.v] && e.cap > e.flow){
vis[e.v] = 1;
d[e.v] = d[u] + 1;
q.push(e.v);
}
}
}
return vis[t];
}
int dfs(int u,int a){
if(u == t || a == 0) return a;
int flow = 0,f,sz = G[u].size();
for(int &i = cur[u];i < sz;i++){
auto &e = edges[G[u][i]];
if(d[u] + 1 == d[e.v] && ((f = dfs(e.v,min(a, e.cap-e.flow)))>0)){
e.flow += f,edges[G[u][i]^1].flow -= f;
flow += f,a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow(int s,int t){
this->s = s,this->t = t;
int flow = 0;
while(bfs()){
memset(cur,0,sizeof(cur));
flow += dfs(s,inf);
}
return flow;
}
}dic;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m,k,x,y,z;
scanf("%d%d%d",&n,&m,&k);
int s = n * m,t = s + 1;
dic.init(n * m + 2);
for(int i = 0;i < n;i++){
dic.add(s,i * m,inf);
for(int j = 0;j < m - 1;j++){
scanf("%d",&x);
dic.add(i * m + j,i * m + j + 1,1000 - x);
}
scanf("%d",&x);
dic.add(i * m + m - 1,t,1000 - x);
}
while(k--){
scanf("%d%d%d",&x,&y,&z);x--,y--;
for(int j = 1;j <= m;j++){
if(j - z > 0){
if(j - z > m) dic.add(x * m + j - 1, t, inf);
else dic.add(x * m + j - 1, y * m + j - z - 1,inf);
}
}
}
int cost = dic.Maxflow(s,t);
if(cost >= inf) cost = -1;
else cost = n * 1000 - cost;
printf("%d
",cost);
}
return 0;
}