HDU 5772 String problem(最大权闭合子图)

题意:

$懒得翻译题目了 - -$

分析:

$最大权闭合子图详细见胡波涛的论文$
$建图就源向正权点连边,容量是正权,负权就负权点向汇连边,容量是负权的绝对值$
$对于原图中依赖关系,保留在网络流图中,容量是INF$
$答案是\sum 正权-最小割$


本题,官方题解写的很清楚了

代码:

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//
// Created by TaoSama on 2016-08-02
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const int M = 1e6 + 10;
//必须添加超源超汇 0->s n+1->t
//特判起终点相同的情况 -> WA
struct Edge {
int v, nxt, cap, flow;
} edge[M];
int head[N], cnt;
void addEdge(int u, int v, int c1) {
edge[cnt] = {v, head[u], c1, 0};
head[u] = cnt++;
edge[cnt] = {u, head[v], 0, 0};
head[v] = cnt++;
}
int lev[N], cur[N];
bool bfs(int s, int t) {
queue<int> q;
memset(lev, 0, sizeof lev);
q.push(s); lev[s] = 1;
while(q.size() && !lev[t]) {
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(edge[i].cap > edge[i].flow && !lev[v]) {
lev[v] = lev[u] + 1;
q.push(v);
}
}
}
return lev[t];
}
int dfs(int u, int t, int delta) {
if(u == t || !delta) return delta;
int ret = 0;
for(int i = cur[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(edge[i].cap > edge[i].flow && lev[v] == lev[u] + 1) {
int d = dfs(v, t, min(delta, edge[i].cap - edge[i].flow));
cur[u] = i;
ret += d; delta -= d;
edge[i].flow += d;
edge[i ^ 1].flow -= d;
if(delta == 0) return ret;
}
}
lev[u] = 0;
return ret;
}
int dinic(int s, int t) {
int ret = 0;
while(bfs(s, t)) {
for(int i = s; i <= t; ++i) cur[i] = head[i];
ret += dfs(s, t, INF);
}
return ret;
}
const int C = 100;
int n, a[C], b[C];
char str[C];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int T; scanf("%d", &T);
while(T--) {
scanf("%d%s", &n, str + 1);
for(int i = 0; i <= 9; ++i) scanf("%d%d", a + i, b + i);
cnt = 0; memset(head, -1, sizeof head);
int s = 0, t = n * n + n + 10 + 1;
//w_ij: 1~n^2 s_i: n^2+1 ~ n^2+n
//10: n^2+n+1 ~ n^2+n+10
int sum = 0;
int delta[] = {0, n * n, n* n + n};
for(int i = 0; i < 10; ++i)
addEdge(delta[2] + i + 1, t, -(a[i] - b[i])); //10 -> t
for(int i = 1; i <= n; ++i) {
addEdge(delta[1] + i, t, a[str[i] - '0']); //s_i -> t
addEdge(delta[1] + i, delta[2] + str[i] - '0' + 1, INF); //s_i -> 10
for(int j = 1; j <= n; ++j) {
int w; scanf("%d", &w);
sum += w;
addEdge(s, (i - 1) * n + j, w); //s -> w_ij
if(i == j) continue;
addEdge((i - 1) * n + j, delta[1] + i, INF); //w_ij -> s_i
addEdge((i - 1) * n + j, delta[1] + j, INF); //w_ij -> s_j
}
}
static int kase = 0;
printf("Case #%d: %d\n", ++kase, sum - dinic(s, t));
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到