「UVALive-7264」Kejin Game(最小割)

发表于 | 分类于 ， ，

「LA-7264」Kejin Game
最小割模型，到达给定点所需的最小花费

题意

游戏内有一个技能树（为DAG），每个技能有一些前置技能，必须先学习完前置技能才能学习当前技能。

你是一个氪金玩家。你可以选择氪金跳过所有前置技能直接学习某个技能；或者氪金切断A到B的边，使技能A不再是B的前置技能（也就意味着学习技能B不再需要先学技能A），并且在学习完所有仍然存在的前置技能（可能为0）后，花费正常的价格学习当前技能。

求习得某个技能$S$所需的最小花费。

题解

对于技能$i$，有两种方式习得该技能：

  1. 直接氪金习得该技能
  2. 切断一些前置技能的边，习得剩下的前置技能(同样可以通过1,2两种方式)，并且花费正常价格学习当前技能

考虑拆点，令点$i+n$为学习技能$i$的最小花费。

对$i$和$i+n$连边，容量为氪金学习该技能的花费；

对$S$和$i$连边，容量为正常价格学习该技能的花费；

对$j+n$和$i$连边，其中$j$为$i$的前置技能，容量为切断$j-i$的花费。

那么$S$到$i+n$的最小割即为”氪金直接学习当前技能“与”切断一部分前置技能，学习剩下的前置技能，正常学习当前技能“的花费当中的较小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 1000 + 10;
const int INF = 0x3f3f3f3f;

//用于表示边的结构体（终点，流量，反向边）
struct edge{int to, cap, rev;};

vector<edge> G[MAX_V];	//图的邻接表表示
int level[MAX_V];	//顶点到源点的距离标号
int iter[MAX_V];	//当前弧

void add(int from, int to, int cap)
{
	G[from].push_back((edge){to, cap, G[to].size()});
	G[to].push_back((edge){from, 0, G[from].size() - 1});
}

//计算从源点出发的距离标号
void bfs(int s)
{
	memset(level, -1, sizeof(level));
	queue<int> que;
	level[s] = 0;
	que.push(s);
	while(!que.empty())
	{
		int v = que.front(); que.pop();
		for(int i = 0; i < G[v].size(); i++)
		{
			edge &e = G[v][i];
			if(e.cap > 0 && level[e.to] < 0)
			{
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}

//通过DFS寻找增广路
int dfs(int v, int t, int f)
{
	if(v == t) return f;
	for(int &i = iter[v]; i<G[v].size(); i++)
	{
		edge &e = G[v][i];
		if(e.cap > 0 && level[v] < level[e.to])
		{
			int d = dfs(e.to, t, min(f, e.cap));
			if(d > 0)
			{
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

//求解从s到t的最大流
int max_flow(int s, int t)
{
	int flow = 0;
	for(;;)
	{
		bfs(s);
		if(level[t] < 0) return flow;
		memset(iter, 0, sizeof(iter));
		int f;
		while((f = dfs(s,t,INF)) > 0) flow += f;
	}
}

int main()
{
    int _, n, m, p, a, b, c;
    scanf("%d", &_);
    while(_ --)
    {
        scanf("%d%d%d", &n, &m, &p);
        int S = 0, T = 2 * n + 1;
        for(int i = 0; i <= T; i ++) G[i].clear();
        while(m --)
        {
            scanf("%d%d%d", &a, &b, &c);
            add(a + n, b, c);
        }
        for(int i = 1; i <= n; i ++) scanf("%d", &c), add(S, i, c);
        for(int i = 1; i <= n; i ++) scanf("%d", &c), add(i, i + n, c);
        add(p + n, T, INF);
        printf("%d\n", max_flow(S, T));
    }
    return 0;
}