首页 > 代码库 > HDU 1565：方格取数(1)（最大点权独立集）***
HDU 1565：方格取数(1)（最大点权独立集）***
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 <cstdio> 2 #include <cstring> 3 #include <queue> 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)（最大点权独立集）***