Menu
Article Graph

HihoCoder 1252 Kejin Game

NodeKey

NodeKey

• 4 min read

网络流建图神题！！！
同时也是2015年北京现场赛的金牌题，虽然我不可能去挑战金牌，但是也只有做这种神题，尽管不是自己想得，但A了之后仍然充满了满足。

题意：
给你一个DAG，表示一个游戏的技能树，也就是说某一些技能存在前置技能，但实际上这是为氪金大佬准备的游戏，有钱是真的可以为所欲为的，大佬们可以选择花钱直接无视所有前置技能直接习得某一个技能，也可以消除掉两个技能之间的依赖关系。

现在某个节俭的大佬想要学某一个技能，问最小花费。

思路：
说实话这道题一眼真的很容易想到图上DP，但是存在可以消除一个依赖的权利，使得DP存在后效性。
正解是最小割建模，这个最小割建模真的是非常巧妙：

  1. 拆点建图，u -> u’ 的容量是直接氪金习得这一技能的花费
  2. 如果u,v存在依赖关系 u -> v ，建边 u’ -> v ，容量为消除这个依赖的费用
  3. 将源点与每一个技能连边，容量为按技能树学习的费用。
  4. 将所要求的技能与汇点相连，容量为 inf

最后跑一遍最大流就是答案。

网上很多题解到这里就没了，也没有一个像样点的解释。

对于学习技能来说，其实就是一个消除依赖的过程，当然你不氪金的话还要花费学习这个技能份额费用，直接将按技能树学习的费用也作为一个依赖，就无需考虑这个，这就是第三条建边规则。
按这么想的话，第一条和第二条也很好理解。
而当我所要学得那个技能的依赖全部消除的时候，那么源点与汇点也就会被分离，也就是被个开了，因为汇点只会与所要求的技能相连。

感觉还是有点说不好啊，如果还不懂的话，只要在纸上画一画，就会变得很显然了。

AC Code

#include 

using namespace std;

const int maxn = 2e3 + 5;
const int maxm = 2e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, src, des, idx;
int cur[maxn], level[maxn], head[maxn];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm  que;

void addEdge(int u, int v, int c)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], 0); //无向图为 c 有向图为 0
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(src);
    level[src] = 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[des] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == des)
        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;
}


<br></br>int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= 2 * n + 2; i++)
            cur[i] = head[i];
        while ((cflow = dfs(src, inf)))
            ans += cflow;
    }
    return ans;
}

void init(int s, int d)
{
    memset(head, -1, sizeof head);
    idx = 0;
    src = s, des = d;
}

inline int in(int x) { return x << 1; }
inline int out(int x) { return x << 1 | 1; }

int main()
{
    int T, u, v, w, t;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &t);
        init(0, 1);
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(out(u), in(v), w);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &w);
            addEdge(src, in(i), w);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &w);
            addEdge(in(i), out(i), w);
        }
        addEdge(out(t), des, inf);
        printf("%d\n", dinic());
    }
    return 0;
}

…………不知道为什么不把代码分开就显示不出来……

Share