(最小割)

题意：

有\(n\)个小朋友，标号为\(1\)到\(n\)，你要给每个小朋友至少\(1\)个且至多\(m\)个的糖果。小朋友们共提出\(k\)个要求，每个要求包括三个整数\(x,y,z\)，表示\(x\)号小朋友得到的糖果数减去\(y\)号小朋友得到的糖果数，结果应当不大于\(z\)。如果你给\(i\)号小朋友\(j\)颗糖果，他会获得\(w_{i,j}\)

的满意度，你需要最大化所有小朋友的满意度之和。\(1\leq n,m\leq50,1\leq k\leq150,1\leq 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
    
     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
     
       edges;    vector
      
        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
       
         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\n",cost);    }    return 0;}