国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > 综合技术 > hdu 1569 方格取数(2) 网络流 最大点权独立集

hdu 1569 方格取数(2) 网络流 最大点权独立集

来源:程序员人生   发布时间:2015-06-06 08:38:24 阅读次数:2541次

方格取数(2)

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5146    Accepted Submission(s): 1610


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

Input
包括多个测试实例,每一个测试实例包括2整数m,n和m*n个非负数(m<=50,n<=50)
 

Output
对每一个测试实例,输出可能获得的最大的和
 

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

Sample Output
188
 

Author
ailyanlu


 

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1569


做法:由于相邻的点是不能同时取的,所以用i+j的奇偶可以分成两类点。然后把相邻的两个点连上边。我们要求的就是取若干个点,且取走的点两两之间没有边,求出其最大的点权和。这个就是求最大点权独立集。  有公式:最大点权独立集=sum-最小点全覆盖集。

最小点权覆盖集,就是取若干个点,这些点覆盖到了所有的边,且所有点的点权和是最小的。

由此可以建边, ss 连向所有(i+j)%2==1的点,边权为这个点的值。   然后将他连向所有相邻的点,边权为inf。然后把(i+j)%2==0的点连向ee,边权为这个点的值。


然后跑出来的就是 最小点全覆盖集 了。 想的话,把最大流 看成最小割,感觉可以想通点,但是不知道怎样说。 

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> using namespace std; #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> const int MAXN = 22222;//点数的最大值 const int MAXM = 22222;//边数的最大值 const int INF = 2000000000; struct Edge { int to,next,cap,flow; }edge[MAXM];//注意是MAXM int tol; int head[MAXN]; int gap[MAXN],dep[MAXN],cur[MAXN]; void init() { tol = 0; memset(head,⑴,sizeof (head)); } void addedge (int u,int v,int w,int rw = 0)//网络流要有反向弧 { edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; } int Q[MAXN]; void BFS(int start,int end) { memset(dep,⑴,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0] = 1; int front = 0, rear = 0; dep[end] = 0; Q[rear++] = end; while(front != rear) { int u = Q[front++]; for(int i = head[u]; i != ⑴; i = edge[i].next) { int v = edge[i]. to; if(dep[v] != ⑴)continue; Q[rear++] = v; dep[v] = dep[u] + 1; gap[dep[v]]++; } } } int S[MAXN]; int sap(int start,int end, int N)//有几个点 { BFS(start,end); memcpy(cur,head,sizeof(head)); int top = 0; int u = start; int ans = 0; int i; while(dep[start] < N) { if(u == end) { int Min = INF; int inser; for( i = 0;i < top;i++) { if(Min > edge[S[i]].cap - edge[S[i]].flow) { Min = edge[S[i]].cap - edge[S[i]].flow; inser = i; } } for( i = 0;i < top;i++) { edge[S[i]]. flow += Min; edge[S[i]^1].flow -= Min; } ans += Min; top = inser; u = edge[S[top]^1].to; continue; } bool flag = false; int v; for( i = cur[u]; i != ⑴; i = edge[i]. next) { v = edge[i]. to; if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]) { flag = true; cur[u] = i; break; } } if(flag) { S[top++] = cur[u]; u = v; continue; } int Min = N; for( i = head[u]; i != ⑴; i = edge[i].next) { if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) { Min = dep[edge[i].to]; cur[u] = i; } } gap[dep[u]]--; if(!gap[dep[u]]) return ans; dep[u] = Min + 1; gap[dep[u]]++; if(u != start)u = edge[S[--top]^1].to; } return ans; } int mp[60][60]; int main() { int n,m,a,b,c; while(scanf("%d%d",&n,&m)!=EOF) { init(); int sum=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",&mp[i][j]); sum+=mp[i][j]; } } int ss=n*m; int ee=n*m+1; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { int nw=i*m+j; if((i+j)%2==1) { addedge(ss,nw,mp[i][j]); if(i!=0) addedge(nw,nw-m,INF); if(j!=0) addedge(nw,nw⑴,INF); if(i!=n⑴) addedge(nw,nw+m,INF); if(j!=m⑴) addedge(nw,nw+1,INF); } else addedge(nw,ee,mp[i][j]); } } printf("%d ",sum-sap(ss,ee,ee+1)); } return 0; } /* 3 3 9999 15 21 75 15 28 34 70 5 */










生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生