[hdu1569]方格取数(2) 最大点权独立集

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

我们首先将棋盘染成二色图（相邻点颜色不同），再将它想象成二分图。

设立一个超级源点与超级汇点，将超级源点与一种颜色相连，另一种颜色与超级汇点相连，容量为格子权值。

再将将相邻的异色格（从连接超级源点的格子到连接超级汇点的格子）之间建立一条容量无限大的边。

我们就可以看出，题目要求求出二分图的最大点权独立集，将其转为二分图最小点权覆盖问题（戳我）。

#include <cstdio>#include <cstring>#include <vector>#include <queue>#define inf 1e9using namespace std;int m,n;int map[55][55];struct Edge{	int to,flow,ro;};vector<Edge> e;vector<int> g[2505];int dis[2505];bool vis[2505];int cur[2505];int tot;int s,ed;void add_edge(int from,int to,int ro){	e.push_back((Edge){to,0,ro});	g[from].push_back(tot);	tot++;	e.push_back((Edge){from,0,0});	g[to].push_back(tot);	tot++;}void build_edge(){	register int i,j;	for (i=1;i<=n;i++)	{		for (j=1;j<=m;j++)		{			int now=(i-1)*m+j;			if ((i+j)%2)			{				add_edge(s,now,map[i][j]);                if(i>1) add_edge(now,now-m,inf);                if(i<n) add_edge(now,now+m,inf);                if(j>1) add_edge(now,now-1,inf);                if(j<m) add_edge(now,now+1,inf);			}			else add_edge(now,ed,map[i][j]);		}	}}bool bfs(int s,int ed){	register int i;	memset(vis,0,sizeof (vis));	queue<int>q;	q.push(s);	vis[s]=1;dis[s]=0;	while (!q.empty())	{		int x=q.front();		q.pop();		for (i=0;i<g[x].size();i++)		{ 			Edge& ee=e[g[x][i]];			if (!vis[ee.to]&&ee.ro>ee.flow)			{				vis[ee.to]=1;				dis[ee.to]=dis[x]+1;				q.push(ee.to);			}		}	}	return vis[ed];}int dfs(int x,int a){	if (x==ed||a==0) return a;	int flow=0,f;	for (int& i=cur[x];i<g[x].size();i++)	{		Edge& ee=e[g[x][i]];		if(dis[x]+1==dis[ee.to]&&(f=dfs(ee.to,min(a,ee.ro-ee.flow)))>0)		{			ee.flow+=f;			e[g[x][i]^1].flow-=f;			flow+=f;			a-=f;			if (a==0) break;		} 	} 	return flow;}int dinic(int s,int ed){	int flow=0;	while (bfs(s,ed))	{		memset(cur,0,sizeof(cur));		flow+=dfs(s,inf);	}	return flow;}int main(){	register int i,j;	while(~scanf("%d%d",&n,&m))	{		memset(dis,0,sizeof(dis));		for (i=0;i<=2503;i++)		{			g[i].clear();		}		e.clear();		tot=0;		int re=0;		for (i=1;i<=n;i++)		for (j=1;j<=m;j++)		{			scanf("%d",&map[i][j]);			re+=map[i][j];		}		s=0,ed=n*m+1;		build_edge();		PRintf("%d/n",re-dinic(s,ed));	}	return 0;}