【最大点权独立集】【HDU1565】【方格取数】

题目大意:

给你一个n*n的格子的棋盘,每个格子里面有一个非负数。

从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。

初看:

没想法中..Orz, 万物皆网络流??

如何构图??如何构图??

以什么为容量? 格子里的数吗?

点呢?

超级源是什么??超级汇是什么??

这特么是网络流??

呜。。好想看题解。。好难。。

再想会。。

拆点?

或者网络流只是辅助 主算法其实是搜索?

想到7点就看题解了。。

最后的脑洞乱开

超级源向所有点连一条容量为格子内数值的边。

然后考虑消除相邻边的影响 能选某个点,必须周围4个都没有被选择

用网络流怎么实现这种操作?感觉不可能。。

好烦,7点了(其实还差5分钟),看题解了。

卧槽

原来是最小割和最大点权独立集

先来补补最大点权独立集的基础知识:

http://yzmduncan.iteye.com/blog/1149057

看完后还有一下难点:为何可以变成二分图?

鸟神告诉我 黑白染色

这又涉及到二分图的定义及判断问题(顺便翻下离散数学复习一下..然而离散并没有..去网上看看..)

---------------------------------------------------------------------------------------------------------------------------------------------------------

二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。

无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。回路就是环路,也就是判断是否存在奇数环。

判断二分图方法:

    用染色法,把图中的点染成黑色和白色。

    首先取一个点染成白色,然后将其相邻的点染成黑色,如果发现有相邻且同色的点,那么就退出,可知这个图并非二分图。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

所以显然可知 该图是二分图,且黑白染色后,黑白即为二分图两端。

求二分图的最大点权独立集

--------------------------------------------------------------------------------------

开始写代码...然后写题解...

s连向白点 流量为白点的值

白点连黑点 流量无穷大

黑点连t   流量黑点的值

求最大流maxflow

ans=sum-maxflow

证明在上面

代码:

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
const int MAXN=400+5;
const int MAXM=10000;
const int INF=0x3f3f3f3f;
int s,t;
struct Edge
{
int to,next,cap,flow;
void get(int a,int b,int c,int d)
{
to=a;next=b;cap=c;flow=d;
}
}edge[MAXM];
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void init()
{
tol=0;
memset(head,-1,sizeof(head));
}
//单向图三个参数,无向图四个参数
void addedge(int u,int v,int w,int rw=0)
{
edge[tol].get(v,head[u],w,0);head[u]=tol++;
edge[tol].get(u,head[v],rw,0);head[v]=tol++;
}
int sap(int start,int end,int N)
{
memset(gap,0,sizeof(gap));
memset(dep,0,sizeof(dep));
memcpy(cur,head,sizeof(head));
int u=start;
pre[u]=-1;
gap[0]=N;
int ans=0;
while(dep[start]<N)
{
if(u==end)
{
int Min=INF;
for(int i=pre[u];i!=-1;i=pre[edge[i^1].to])
if(Min>edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
for(int i=pre[u];i!=-1;i=pre[edge[i^1].to])
{
edge[i].flow+=Min;
edge[i^1].flow-=Min;
}
u = start;
ans+=Min;
continue;
}
bool flag=false;
int v;
for(int i=cur[u];i !=-1;i=edge[i].next)
{
v=edge[i].to;
if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u])
{
flag=true;
cur[u]=pre[v]=i;
break;
}
}
if(flag)
{
u=v;
continue;
}
int Min=N;
for(int i=head[u];i!=-1;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[pre[u]^1].to;
}
return ans;
}
//new type
void INIT()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int n;
int sum;
int map[30][30];
int T[30][30];
int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};
void input()
{
init();
sum=0;
memset(T,0,sizeof(T));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
T[i][j]=(i-1)*n+j;
sum+=map[i][j];
}
}
void solve()
{
s=0;t=n*n+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if((i+j)%2==0)
{
addedge(s,T[i][j],map[i][j]);
for(int k=0;k<4;k++)
{
if(T[i+fx[k]][j+fy[k]]!=0)
addedge(T[i][j],T[i+fx[k]][j+fy[k]],INF);
}
}
else
{
addedge(T[i][j],t,map[i][j]);
}
} }
int main()
{
// INIT();
while(cin>>n)
{
int ans;
input();
solve();
ans=sap(s,t,n*n+2);
printf("%d\n",sum-ans);
}
}

上一篇:2015第14周五Tomcat版本


下一篇:图的遍历(bfs 和dfs)