首页 > 代码库 > HDU 1565 && HDU 1569 方格取数 (网络流之最小割)
HDU 1565 && HDU 1569 方格取数 (网络流之最小割)
题目地址:HDU 1565 HDU 1569
刚开始接触最小割,就已经感受到了最小割的博大精深。。。
这建图思路倒是好想。。因为好多这种关于不相邻的这种网络流都是基本都是这样建图。但是感觉毫无道理可言。。。看了题解后才明白这样做的意义。
下面是题解中的说法。
大概是这样分析的,题义是要我们求在一个方格内取出N个点,使得这N个独立的(不相邻)点集的和最大。我们可以将问题转化为最小割来求解。首先,我们将方格进行黑白相间的染色,然后再将任意一种颜色(黑色)作为源点,一种颜色(白色)作为汇点。我们的算法过程就是一个不断寻找增广路的过程。当我们找到最大流的时,也就是此时不存在从黑色到白色的路径,也即不存在不相邻的两个方格能够连通了。而此时的最大流就是分割两个区间的最小割,拿总合值减去这个最小割就是我们想要得到的结果。
题解上已经说的很清楚了。我还要补充的是,这是属于最大点权独立集。
最大点权独立集。多和最小点权覆盖集放到一起使用。分别求图中不相邻的点权最大/或者边中至少有一点在集合中,求最小总权值的问题。
公式:
最大点权独立集=总权值-最小点权覆盖集。
最小点权覆盖集=图的最小割值=最大流。
代码如下:(以1569的代码为例)#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include<algorithm> using namespace std; const int INF=0x3f3f3f3; int head[3000], source, sink, cnt, nv, mp[60][60]; int cur[3000], num[3000], d[3000], pre[3000]; int jx[]={0,0,1,-1}; int jy[]={1,-1,0,0}; struct node { int u, v, cap, next; }edge[10000000]; void add(int u, int v, int cap) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].next=head[v]; head[v]=cnt++; } void bfs() { memset(d,-1,sizeof(d)); memset(num,0,sizeof(num)); queue<int>q; q.push(sink); d[sink]=0; num[0]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(d[v]==-1) { d[v]=d[u]+1; num[d[v]]++; q.push(v); } } } } int isap() { memcpy(cur,head,sizeof(cur)); bfs(); int flow=0, u=pre[source]=source, i; while(d[source]<nv) { if(u==sink) { int f=INF, pos; for(i=source;i!=sink;i=edge[cur[i]].v) { if(f>edge[cur[i]].cap) { f=edge[cur[i]].cap; pos=i; } } for(i=source;i!=sink;i=edge[cur[i]].v) { edge[cur[i]].cap-=f; edge[cur[i]^1].cap+=f; } flow+=f; u=pos; } for(i=cur[u];i!=-1;i=edge[i].next) { if(d[edge[i].v]+1==d[u]&&edge[i].cap) { break; } } if(i!=-1) { cur[u]=i; pre[edge[i].v]=u; u=edge[i].v; } else { if(--num[d[u]]==0) break; int mind=nv; for(i=head[u];i!=-1;i=edge[i].next) { if(mind>d[edge[i].v]&&edge[i].cap) { mind=d[edge[i].v]; cur[u]=i; } } d[u]=mind+1; num[d[u]]++; u=pre[u]; } } return flow; } int main() { int n, i, j, sum, ans, m; while(scanf("%d%d",&n,&m)!=EOF) { sum=0; memset(head,-1,sizeof(head)); cnt=0; for(i=0;i<n;i++) { for(j=0;j<m;j++) { scanf("%d",&mp[i][j]); sum+=mp[i][j]; } } source=0; sink=n*m+1; nv=sink+1; for(i=0;i<n;i++) { for(j=0;j<m;j++) { if((i+j)%2) { add(source,i*m+j+1,mp[i][j]); for(int k=0;k<4;k++) { int x=i+jx[k]; int y=j+jy[k]; if(x>=0&&x<n&&y>=0&&y<m) { add(i*m+j+1,x*m+y+1,mp[i][j]); } } } else { add(i*m+j+1,sink,mp[i][j]); } } } ans=isap(); printf("%d\n",sum-ans); } return 0; }
HDU 1565 && HDU 1569 方格取数 (网络流之最小割)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。