例行废话
哇～，惊了，多校里面第一次出现网络流的题目。然而我并没有时间甚至没有看它一眼……
我学了这么久的图论究竟是为了什么呢……
老实说我有一种不详的预感
现在想想的确是这样的，自己努力钻研的高级算法，又有多少会在比赛中用到呢……
回归正题
这是一道最小割+差分约束的题目，还是第一次遇到这两个结合起来。不过其实也只是分开来的问题，用差分约束判断可行性，再用最小割求解。
题意：
你要给( n) 个小朋友糖果，最少( 1)个，最多( m )个，并且你手上有无穷多的糖。并不是说给一个小朋友的糖果越多越好，给每一个小朋友不同糖果数量对应的愉悦值不同。我们自然希望小朋友的愉悦值最大化。
但这些小朋友也提出了一些要求，对于每一个要求( ( x , y , z ) )，你给 ( x) 的糖果数量 ( ax ) 与给( y) 的糖果数量( ay) 满足如下不等式 ( ax – ay \leq z )。
问满足所有要求的最大愉悦值。
若无法满足，输出-1。
思路：
关于满足小朋友们的要求：
这是整个问题的一个子问题，每个要求都是一个不等式，我们很自然地能够想到用差分约束去判断可行性。这个子问题是个差分约束的裸问题，这里不再赘述。
关于最小割建图：
先直接上建图方式，下面有解释。
设源点( S ) ，汇点( T) ，( ( a , b ) )表示给小朋友( a) 糖果 ( b ) 颗。
( a \rightarrow b == c ) 表示 ( a) 与 ( b) 建边，容量为 ( c )。
- 对于每一个小朋友 ( p) ( S \rightarrow ( p, 1 ) == inf , ( p , m ) \rightarrow T ==inf )
- 对于每一个小朋友 ( p) 的每一个给定糖果数量 ( k) 所得的愉悦值 ( w) ，( ( p, k ) \rightarrow ( p , k+1 ) )，注意后面不能越界。
- 对于每一个限制要求 ( ax – ay \leq z )，再对于范围内的糖果数量 ( i) ，建边( ( x , i + z ) \rightarrow ( y , i ) == inf )
因为给每个小朋友的糖果数量 ( w \leq 1000 ) 。( 题面上并没有说明，但是题解上说了…… )
那么我们可以这么想，我先给每个小朋友 1000 个糖果，然后再从小朋友中拿回一些糖果，我们要求最大值，自然是使得拿回的糖果造成的愉悦值减少最小，对于一个小朋友来说这就是一条割边。因为每个小朋友都要拿回糖果，所以对于整张图来说就是最小割了。
再是对每一个限制要求：写个题解好累，能自己理解去么……
对于( (x , i + z ) \rightarrow ( y , i ) ) 可以这样想，如果我割掉了 ( ( x, i + z – 1 ) \rightarrow ( x , i + z ) ) ，那么如果你在 ( y)不选择( ( y, i ) ) 之后的边，那么上面那个割边就变的没有意义，从而你必须去割掉一条 ( inf) 的边。
哎呀，自己在纸上画画就很清楚了……
AC Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
const int maxv = 55;
const int maxn = maxv * maxv;
const int maxm = maxn * maxn;
const int inf = 0x3f3f3f3f;
int n, m, k, st, en, idx;
int cur[maxn], level[maxn], head[maxn];
int kvis[maxv];
int mat[maxv][maxv];
int ku[155], kv[155], kw[155];
vector<pii> G[55];
struct node {
int to, next;
int cap;
node() {}
node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];
queue<int> que;
stack<int> stk;
inline int getNode(int a, int b) { return a * m + b; }
void addEdge(int u, int v, int c, int rc = 0)
{
edges[idx] = node(v, head[u], c);
head[u] = idx++;
edges[idx] = node(u, head[v], rc);
head[v] = idx++;
}
bool bfs()
{
memset(level, -1, sizeof level);
que.push(st);
level[st] = 0;
int u;
while (!que.empty()) {
u = que.front();
que.pop();
for (int id = head[u]; ~id; id = edges[id].next) {
int v = edges[id].to;
if (edges[id].cap > 0 && level[v] == -1) {
level[v] = level[u] + 1;
que.push(v);
}
}
}
return level[en] != -1;
}
int dfs(int u, int low)
{
int cflow;
if (u == en)
return low;
for (int& id = cur[u]; ~id; id = edges[id].next) {
int v = edges[id].to;
if (edges[id].cap > 0 && level[v] == level[u] + 1
&& (cflow = dfs(v, min(low, edges[id].cap)))) {
edges[id].cap -= cflow;
edges[id ^ 1].cap += cflow;
return cflow;
}
}
return 0;
}
int dinic()
{
int ans = 0, cflow;
while (bfs()) {
for (int i = 0; i <= en; i++)
cur[i] = head[i];
while ((cflow = dfs(st, inf)))
ans += cflow;
}
return ans;
}
void Ginit()
{
memset(kvis, false, sizeof kvis);
for (int i = 0; i < n; i++)
G[i].clear();
}
void init(int s, int e)
{
st = s, en = e;
memset(head, -1, sizeof head);
idx = 0;
}
bool spfa(int st)
{
bool vis[maxv];
int dis[maxv], cnt[maxv];
for (int i = 0; i <= n; i++) {
cnt[i] = vis[i] = false;
dis[i] = inf;
}
while (!stk.empty())
stk.pop();
dis[st] = 0, kvis[st] = vis[st] = true, cnt[st] = 1;
stk.push(st);
while (!stk.empty()) {
int u = stk.top(), sz = G[u].size();
stk.pop();
vis[u] = false;
for (int i = 0; i < sz; i++) {
int v = G[u][i].first;
if (dis[v] > dis[u] + G[u][i].second) {
dis[v] = dis[u] + G[u][i].second;
if (!vis[v]) {
kvis[v] = vis[v] = true;
stk.push(v);
if (++cnt[v] > n)
return false;
}
}
}
}
return true;
}
void CreateGragh()
{
m++;
init(n * m, n * m + 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++)
addEdge(getNode(i, j), getNode(i, j + 1), 1000 - mat[i][j]);
addEdge(st, getNode(i, 0), inf);
addEdge(getNode(i, m - 1), en, inf);
}
for (int p = 0; p < k; p++) {
for (int i = 0; i + kw[p] < m; i++)
addEdge(getNode(ku[p], i + kw[p]), getNode(kv[p], i), inf);
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &mat[i][j]);
Ginit();
for (int i = 0; i < k; i++) {
scanf("%d %d %d", ku + i, kv + i, kw + i);
ku[i]--, kv[i]--;
G[ku[i]].push_back(make_pair(kv[i], kw[i]));
}
bool flag = false;
for (int i = 0; i < n && !flag; i++)
if (!kvis[i])
if (!spfa(i)) {
flag = true;
break;
}
if (flag) {
puts("-1");
continue;
}
CreateGragh();
int key = dinic();
printf("%d\n", 1000 * n - key);
}
return 0;
}