端点 mbo void scan 补集 web ring rgba
http://acm.hdu.edu.cn/showproblem.php?pid=1565
题意:中文。
思路:一个棋盘,要使得相邻的点不能同时选,问最大和是多少,这个问题就是最大点权独立集。
可以转化为所有的点权 - 最小点权覆盖集(最小割) = 最大点权独立集。
转载两个的定义:这里。
覆盖集(vertex covering set,VCS)是无向图的一个点集,使得该图中所有边都至少有一个端点在该集合内。形式化的定义是点覆盖集为 G'VV∈(,)uvE∀∈,满足对于,都有 或成立,即,'uV∈'vV∈'uV∈'vV∈至少一个成立。形象地说是若干个点 "覆盖" 住了 与它们邻接的边,这些边恰好组成了原边集。
点独立集(vertex independent set,VIS)是无向图的一个点集,使得任两个在该集合中的点在原图中都不相邻。或者说是导出子图为零图(没有边)的点集。形式化的定义是点独立集为,满足对于,都有 G'VV∈,'uvV∀∈(,)uvE∉成立。点独立集还有一种等价的定义:点独立集为,满足对于,都有'VV∈'uV∈'vV∈(,)uvE∀∈与不同时成立。
从覆盖集的定义可以看出,求覆盖集就是求最小割(最大流),这个最小点权覆盖集不是 S 集合就是 T 集合,最大权独立集就是最小点权覆盖集的补集。
因此把棋盘通过黑白染色:
设一种颜色和 S 相连(容量为点权),然后用这种颜色去连接相邻另一种颜色(容量为 INF),另一种颜色和 T 相连(容量为点权)。
- 1#include 2#include 3#include 4 using namespace std;
- 5#define N 510 6#define INF 0x3f3f3f3f 7 typedef long long LL;
- 8 struct Edge {
- 9 int v,
- nxt,
- cap;
- 10 Edge() {}
- 11 Edge(int v, int nxt, int cap) : v(v),
- nxt(nxt),
- cap(cap) {}
- 12
- }
- edge[N * N];
- 13 int head[N],
- tot,
- dis[N],
- cur[N],
- pre[N],
- gap[N],
- n,
- mp[25][25],
- dx[] = {
- 0,
- 0,
- 1,
- -1
- },
- dy[] = {
- 1,
- -1,
- 0,
- 0
- };
- 14 15 bool check(int x, int y) {
- 16
- if (1 <= x && x <= n && 1 <= y && y <= n) return true;
- 17
- return false;
- 18
- }
- 19 20 void Add(int u, int v, int cap) {
- 21 edge[tot] = Edge(v, head[u], cap);
- head[u] = tot++;
- 22 edge[tot] = Edge(u, head[v], 0);
- head[v] = tot++;
- 23
- }
- 24 25 int BFS(int S, int T) {
- 26 queue < int > que;
- que.push(T);
- 27 memset(dis, INF, sizeof(dis));
- 28 memset(gap, 0, sizeof(gap));
- 29 gap[0]++;
- dis[T] = 0;
- 30
- while (!que.empty()) {
- 31 int u = que.front();
- que.pop();
- 32
- for (int i = head[u];~i; i = edge[i].nxt) {
- 33 int v = edge[i].v;
- 34
- if (dis[v] == INF) {
- 35 dis[v] = dis[u] + 1;
- 36 gap[dis[v]]++;
- 37 que.push(v);
- 38
- }
- 39
- }
- 40
- }
- 41
- }
- 42 43 LL ISAP(int S, int T, int n) {
- 44 BFS(S, T);
- 45 memcpy(cur, head, sizeof(cur));
- 46 int u = pre[S] = S,
- i,
- index,
- flow;
- LL ans = 0;
- 47
- while (dis[S] < n) {
- 48
- if (u == T) {
- 49 flow = INF,
- index = S; // index = S !!!
- 50
- for (i = S; i != T; i = edge[cur[i]].v) 51
- if (flow > edge[cur[i]].cap) flow = edge[cur[i]].cap,
- index = i;
- 52
- for (i = S; i != T; i = edge[cur[i]].v) 53 edge[cur[i]].cap -= flow,
- edge[cur[i] ^ 1].cap += flow;
- 54 ans += flow,
- u = index;
- 55
- }
- 56
- for (i = cur[u];~i; i = edge[i].nxt) 57
- if (edge[i].cap > 0 && dis[edge[i].v] == dis[u] - 1) break;
- 58
- if (~i) {
- 59 pre[edge[i].v] = u;
- cur[u] = i;
- u = edge[i].v;
- 60
- } else {
- 61
- if (--gap[dis[u]] == 0) break;
- 62 int md = n;
- 63
- for (i = head[u];~i; i = edge[i].nxt) 64
- if (md > dis[edge[i].v] && edge[i].cap > 0) md = dis[edge[i].v],
- cur[u] = i;
- 65 gap[dis[u] = md + 1]++;
- 66 u = pre[u];
- 67
- }
- 68
- }
- 69
- return ans;
- 70
- }
- 71 72 int main() {
- 73
- while (~scanf("%d", &n)) {
- 74 memset(head, -1, sizeof(head));
- tot = 0;
- 75 int S = 0,
- T = n * n + 1;
- LL sum = 0;
- 76
- for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &mp[i][j]),
- sum += mp[i][j];
- 77
- for (int i = 1; i <= n; i++) {
- 78
- for (int j = 1; j <= n; j++) {
- 79
- if ((i + j) % 2) Add(S, (i - 1) * n + j, mp[i][j]);
- 80
- else Add((i - 1) * n + j, T, mp[i][j]);
- 81
- for (int k = 0; k < 4; k++) {
- 82 int nx = i + dx[k],
- ny = j + dy[k];
- 83
- if (check(nx, ny) && (i + j) % 2) Add((i - 1) * n + j, (nx - 1) * n + ny, INF);
- 84
- }
- 85
- }
- 86
- }
- 87 printf("%lld\n", sum - ISAP(S, T, T + 1));
- 88
- }
- 89
- return 0;
- 90
- }
点覆盖集
(
vertex covering set
,
VCS
)是无向图
的一个点集,使得该图中所有边都至少
有一个端点在该集合内。形式化的定义是点覆盖集为
G
'
V
V
∈
(
,
)
u
v
E
∀
∈
,满足对于
,都有
或
成立,即
,
'
u
V
∈
'
v
V
∈
'
u
V
∈
'
v
V
∈
至少一个成立。形象地说是若干个点 "覆盖" 住了
与它们邻接的边,这些边恰好组成了原边集。
点独立集
(
vertex independent set
,
VIS
)是无向图
的一个点集,使得任两个在该集合中
的点在原图中都不相邻。或者说是导出子图为零图(没有边)的点集。形式化的定义是点独
立集为
,满足对于
,都有
G
'
V
V
∈
,
'
u
v
V
∀
∈
(
,
)
u
v
E
∉
成立。点独立集还有一种等价的定义:
点独立集为
,满足对于
,都有
'
V
V
∈
'
u
V
∈
'
v
V
∈
(
,
)
u
v
E
∀
∈
与
不同时成立。
HDU 1565:方格取数 (1)(最大点权独立集)***
来源: http://www.bubuko.com/infodetail-2042782.html