首页 > 代码库 > hdu1565方格取数(1)【最大流||最大点权独立集】

hdu1565方格取数(1)【最大流||最大点权独立集】

2024-07-06 05:14:30   221人阅读

Problem Description
给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
 

 

Input
包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)
 

 

Output
对于每个测试实例，输出可能取得的最大的和
 

 

Sample Input
3 75 15 21 75 15 28 34 70 5
 

 

Sample Output
188

 

 
预备知识：
对于一个无向图G，点有各自的权值
 
点覆盖集：一个点集，使G中所有的边至少有一个点在该集合内
最小点权覆盖集：权值和最小的点覆盖集
 
点独立集：一个点集，该集合中任意两个点都没有边相连
最大点权独立集：全职和最大的点独立集
 
定理：
1、最小点权覆盖集 = 最小割 = 最大流
2、最大点权独立集 = 总权值 - 最小点权覆盖集
 
分析：
该题是二分图中的最大点权独立集的题目
可以用网络流来做
将每个格子抽象成一个点，相邻格子分别涂成黑色和白色
将源点和白色点连一条边，权值为白色点的权值
将白点和它所能到达的白点连一条边，权值为INF
将黑点和汇点连一条边，权值为黑点的权值
这样求出来的网络流便是最小点权覆盖集
然后用总权值减去即可
细节处理：将图上的各点先转化为数字，奇数行奇数列上的点跟偶数行偶数列上的点是同色的
 
代码：
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  5 #include <queue>
  6 using namespace std;
  7 
  8 const int maxn = 205 << 1;
  9 const int INF = 1000000000;
 10 
 11 int map[25][25], a[25][25];
 12 int xx[4] = { 0, 0, 1, -1 };
 13 int yy[4] = { 1, -1, 0, 0 };
 14 
 15 struct Edge
 16 {
 17     int from, to, cap, flow;
 18 };
 19 
 20 struct Dinic
 21 {
 22     int n, m, s, t;
 23     vector<Edge> edges;
 24     vector<int>G[maxn];
 25     bool vis[maxn];
 26     int d[maxn];
 27     int cur[maxn];
 28 
 29     void ClearAll(int n) {
 30         for(int i = 0; i <= n; i++) {
 31             G[i].clear();
 32         }
 33         edges.clear();
 34     }
 35 
 36     void AddEdge(int from, int to, int cap) {
 37         edges.push_back((Edge){from, to, cap, 0} );
 38         edges.push_back((Edge){to, from, 0, 0} );
 39         m = edges.size();
 40         G[from].push_back(m - 2);
 41         G[to].push_back(m - 1);
 42         //printf("%din end\n",m);
 43     }
 44 
 45     bool BFS()
 46     {
 47         memset(vis, 0, sizeof(vis) );
 48         queue<int> Q;
 49         Q.push(s);
 50         vis[s] = 1;
 51         d[s] = 0;
 52         while(!Q.empty() ){
 53             int x = Q.front(); Q.pop();
 54             for(int i = 0; i < G[x].size(); i++) {
 55                 Edge& e = edges[G[x][i]];
 56                 if(!vis[e.to] && e.cap > e.flow) {
 57                     vis[e.to] = 1;
 58                     d[e.to] = d[x] + 1;
 59                     Q.push(e.to);
 60                 }
 61             }
 62         }
 63         return vis[t];
 64     }
 65 
 66     int DFS(int x, int a) {
 67         if(x == t || a == 0) return a;
 68         int flow = 0, f;
 69         for(int& i = cur[x]; i < G[x].size(); i++) {
 70             Edge& e = edges[G[x][i]];
 71             if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
 72                 e.flow += f;
 73                 edges[G[x][i]^1].flow -= f;
 74                 flow += f;
 75                 a -= f;
 76                 if(a == 0) break;
 77             }
 78         }
 79         return flow;
 80     }
 81 
 82     int MaxFlow(int s, int t) {
 83         this -> s = s; this -> t = t;
 84         int flow = 0;
 85         while(BFS()) {
 86             memset(cur, 0, sizeof(cur));
 87             flow += DFS(s, INF);
 88         }
 89         return flow;
 90     }
 91 };
 92 
 93 Dinic g;
 94 
 95 int main() {
 96     int n;
 97     //freopen("b.txt","r",stdin);
 98     while(EOF != scanf("%d",&n) ) {
 99         int tot = 1;
100         int sum = 0;
101         int s = 0; int t = n * n + 1;
102         for(int i = 1;i <= n; i++) {
103             for(int j = 1; j <= n; j++) {
104                 scanf("%d",&a[i][j]);
105                 sum += a[i][j];
106                 map[i][j] = tot++;
107             }
108         }
109         g.ClearAll(maxn);
110         for(int i = 1; i <= n; i++) {
111             for(int j = 1; j <= n; j++) {
112 
113                 if(i % 2 == 1 && j % 2 == 1) {
114                     g.AddEdge(s, map[i][j], a[i][j]);
115                     for(int k = 0; k < 4; k++) {
116                         int tmpx = i + xx[k]; int tmpy = j + yy[k];
117                         if(tmpx >= 1 && tmpx <= n && tmpy >= 1 && tmpy <= n) {
118                             g.AddEdge(map[i][j], map[tmpx][tmpy], INF);
119                             //printf("%d %d %d\n",tmpx, tmpy, map[tmpx][tmpy]);
120                         }
121                     }
122                 }
123 
124                 if(i % 2 == 0 && j % 2 == 0) {
125                     g.AddEdge(s, map[i][j], a[i][j]);
126                     for(int k = 0; k < 4; k++) {
127                         int tmpx = i + xx[k]; int tmpy = j + yy[k];
128                         if(tmpx >= 1 && tmpx <= n && tmpy >= 1 && tmpy <= n) {
129                             g.AddEdge(map[i][j], map[tmpx][tmpy], INF);
130                         }
131                     }
132                 }
133 
134                 if(i % 2 == 1 && j % 2 == 0) {
135                     g.AddEdge(map[i][j], t, a[i][j]);
136                 }
137                 if(i % 2 == 0 && j % 2 == 1) {
138                     g.AddEdge(map[i][j], t, a[i][j]);
139                 }
140             }
141         }
142         //printf("%d %d\n",sum, g.MaxFlow(s, t));
143         printf("%d\n",sum - g.MaxFlow(s, t) );
144     }
145     return 0;
146 }
View Code

 


联系
我们