hdu 1569 方格取数(2)

二分图。

最大点权独立集=总权-最小点权覆盖集。

哪位大神能给一些二分图 最大点权独立集等等 的相关资料!!!!!跪谢


用网络流求解最小点权覆盖集即可,建图不讲了。


#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

#define min(a,b) a>b?b:a
const int maxn=2550,maxm=500000,inf=1000000000;

struct Edge
{
	int v,f,nxt;
};

int g[maxn+50];
int nume;
struct Edge e[maxm+50];
int number[70][70];
int m,n;
int src,sink;
bool vis[maxn+10];
int dist[maxn+10];

void add(int u,int v,int f)
{
	e[++nume].v=v;
	e[nume].f=f;
	e[nume].nxt=g[u];
	g[u]=nume;
	e[++nume].v=u;
	e[nume].f=0;
	e[nume].nxt=g[v];
	g[v]=nume;
}

bool is_n(int  y)
{
	if(y>=1&&y<=n) return true;
	return false;
}

bool is_m(int x)
{
	if(x>=1&&x<=m) return true;
	return false;
}
void Init()
{
	int i,j;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			if((i+j)%2==0){
				add(0,(i-1)*n+j,number[i][j]);
				int tempy1=j-1;
				int tempy2=j+1;
				if(is_n(tempy1)) add((i-1)*n+j,(i-1)*n+tempy1,inf);
				if(is_n(tempy2)) add((i-1)*n+j,(i-1)*n+tempy2,inf);
				int tempx1=i-1;
				int tempx2=i+1;
				if(is_m(tempx1)) add((i-1)*n+j,(tempx1-1)*n+j,inf);
				if(is_m(tempx2)) add((i-1)*n+j,(tempx2-1)*n+j,inf);
			}			
			else add((i-1)*n+j,sink,number[i][j]);
		}
}

void bfs()
{
	int i;
	queue<int >que;
	memset(dist,0,sizeof(dist));
	while(!que.empty()) que.pop();
	que.push(src);
	vis[src]=true;
	while(!que.empty()){
		int u=que.front();
		que.pop();
		for(i=g[u];i;i=e[i].nxt){
			if(e[i].f && !vis[e[i].v]){
				dist[e[i].v]=dist[u]+1;
				que.push(e[i].v);
				vis[e[i].v]=true;
			}
		}
	}
}

int dfs(int u,int delta)
{
	int i;
	if(u==sink) return delta;
	else{
		int ret=0;
		for(i=g[u];i&δi=e[i].nxt){
			if(e[i].f&&dist[e[i].v]==dist[u]+1){
				int dd=dfs(e[i].v,min(delta,e[i].f));
				e[i].f-=dd;
				e[i^1].f+=dd;
				delta-=dd;
				ret+=dd;
			}
		}
		return ret;
	}
}
int dinic()
{
	int ret=0;
	while(true){
		memset(vis,0,sizeof(vis));
		bfs();
		if(!vis[sink]) return ret;
		ret+=dfs(src,inf);
	}
}

int main()
{
	int i,j;
	while(scanf("%d%d",&m,&n)!=EOF){
		nume=1;
		src=0;sink=n*m+1;
		memset(g,0,sizeof(g));
		int sum=0;
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++){
				scanf("%d",&number[i][j]);
				sum+=number[i][j];
			}
		Init();
		printf("%d\n",sum-dinic());
	}
	return 0;
}


hdu 1569 方格取数(2)

上一篇:Java IO流 01 File 类


下一篇:软件研发管理之版本管理