网络流建图神题!!!
同时也是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;
}


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; }

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


发表评论

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

Related Posts

最小割

51Nod 1499 图

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

最小割

HDU 6126 Give out candies

例行废话 哇~,惊了,多校里面第一次出现网络流的题目。然而我并没有时间 Read more…

最小割

ZOJ 3475 The Great Wall I

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