Table of contents

例行废话

哇~,惊了,多校里面第一次出现网络流的题目。然而我并没有时间甚至没有看它一眼……

我学了这么久的图论究竟是为了什么呢……
老实说我有一种不详的预感

现在想想的确是这样的,自己努力钻研的高级算法,又有多少会在比赛中用到呢……

回归正题

这是一道最小割+差分约束的题目,还是第一次遇到这两个结合起来。不过其实也只是分开来的问题,用差分约束判断可行性,再用最小割求解。

题意:
你要给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 表示 ab 建边,容量为 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

最小割

51Nod 1499 图

emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易 Read more…

最小割

HihoCoder 1252 Kejin Game

网络流建图神题!!! 同时也是2015年北京现场赛的金牌题,虽然我不可 Read more…

最小割

ZOJ 3475 The Great Wall I

最小割建图好题!! 昨天比赛的最小割,当时没看出来,实际上需要建图转化 Read more…