选择若干个节点，使得所有的后继节点都在图中
Clever King
题目要求就是生产若干个产品，他们之间有一定的依赖关系，问最后怎么获得的值最大
一道裸的最大权闭合子图的题目
求解：
对于增加收益的连一条从s->i的边，容量为收益
对于花费连一条从i->t的边，容量为花费
他们之间原来的依赖关系，一概连一条容量为正无穷的边
统计收益为sum, 对改图跑最大流
答案为sum-最小割 = sum-maxflow
最大闭合子图建图过程
ac code
注意会爆ll
最大权封闭子图
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
99
100
101
102
103
104
105
106
107
108
109
110
111
using namespace std;
typedef long long ll;
const int maxn = 505;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct Edge{
int to, rev;
ll cap;
Edge(int _to, ll _cap, int _rev):to(_to), cap(_cap), rev(_rev){}
};
vector<Edge> G[maxn];
int cnt[maxn];
int level[maxn];
int s, t;
int n, m;
void add_edge(int u, int v, ll cap){
G[u].push_back(Edge(v, cap, G[v].size()));
G[v].push_back(Edge(u, 0, G[u].size()-1));
}
void bfs(int s){
memset(level, -1, sizeof(level));
queue<int> q;
q.push(s);
level[s] = 0;
while(!q.empty()){
int v = q.front();
q.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;
q.push(e.to);
}
}
}
}
ll dfs(int v, int t, ll flow){
if(v == t) return flow;
for(int& i=cnt[v]; i<G[v].size(); i++){
Edge& e = G[v][i];
if(e.cap>0&&level[v]<level[e.to]){
ll d = dfs(e.to, t, min(flow, e.cap));
if(d>0){
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;//一旦有一条路径满足就立即返回！
}
}
}
return 0;
}
ll max_flow(int s, int t){
ll flow = 0;
for(;;){
//构造层次图
bfs(s);
//无法连通终点，结束访问
if(level[t]<0) return flow;
ll f;
//cnt数组记录在递归的过程中的边的顺序。
memset(cnt, 0, sizeof(cnt));
//当存在增广路的时候不断的进行增广
while((f = dfs(s, t, INF))>0){
flow+=f;
}
}
}
int main()
{
int _;
scanf("%d", &_);
while(_--){
scanf("%d%d", &n, &m);
s = 0;
t = n+m+1;
ll sum = 0;
for(int i=0; i<=n+m+1; i++) G[i].clear();
int u, v;
ll cap;
//连正权值的边
for(int i=1; i<=n; i++){
scanf("%lld", &cap);
sum += cap;
add_edge(s, i, cap);
}
int n1, n2;
//连负权值的边
for(int i=1; i<=m; i++){
scanf("%lld", &cap);
add_edge(i+n, t, cap);
}
//连原图中的边的关系
for(int i=1; i<=n; i++){
scanf("%d%d", &n1, &n2);
for(int j=1; j<=n1; j++){
scanf("%d", &u);
add_edge(i, u+n, INF);
}
for(int j=1; j<=n2; j++){
scanf("%d", &u);
add_edge(i, u, INF);
}
}
printf("%lld\n", sum - max_flow(s, t));
}
return 0;
}
本文标题:最大权封闭子图
文章作者:Babydragon
发布时间:2018-09-19, 01:08:36
最后更新:2018-09-19, 01:16:06
原始链接:http://baolintian.github.io/2018/09/19/最大权封闭子图/
许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。