bzoj 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场最小点覆盖

链接

1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场

思路

这就是个上一篇的稍微麻烦版(是变脸版，其实没麻烦)

用边长为1的模板覆盖地图上的没有长草的土地，不能覆盖草地

每个点(x,y)只有选择x或者y才能被覆盖

还是最小点覆盖，证明在上一篇

横边和竖边得遍历一遍求出，因为不能越过草地嘛

然后左边横边，右边竖边，开心的跑最大流就可以

代码

#include <bits/stdc++.h>

#define iter vector<int>::iterator

using namespace std;

const int N=5e5+7,inf=0x3f3f3f3f;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int n,m,S,T;

struct node {

	int v,nxt,cap;

}e[N<<1];

int head[N<<1],tot=1;

void add_edge(int u,int v,int cap) {

	e[++tot].v=v;

	e[tot].cap=cap;

	e[tot].nxt=head[u];

	head[u]=tot;

}

void Add(int u,int v,int cap) {

	add_edge(u,v,cap);

	add_edge(v,u,0);

}

int dis[N];

bool bfs() {

	memset(dis,-1,sizeof(dis));

	queue<int> q;

	q.push(S);

	dis[S]=0;

	while(!q.empty()) {

		int u=q.front();

		q.pop();

		for(int i=head[u];i;i=e[i].nxt) {

			int v=e[i].v;

			if(dis[v]==-1&&e[i].cap) {

				dis[v]=dis[u]+1;

				q.push(v);

			}

		}

	}

	return dis[T]!=-1;

}

int dfs(int u,int f) {

	if(u==T) return f;

	int rest=f;

	for(int i=head[u];i;i=e[i].nxt) {

		int v=e[i].v;

		if(dis[v]==dis[u]+1&&e[i].cap&&rest) {

			int t=dfs(v,min(e[i].cap,rest));

			if(!t) dis[v]=0;

			e[i].cap-=t;

			e[i^1].cap+=t;

			rest-=t;

		}

	}

	return f-rest;

}

int dinic() {

	int ans=0;

	while(bfs())

		ans+=dfs(S,inf);

	return ans;

}

char s[100][100];

vector<int> dsr,mmp;

int a[100][100],b[100][100],js;

int main() {

	n=read(),m=read();

	for(int i=1;i<=n;++i) scanf("%s",s[i]+1);

	for(int i=1;i<=n;++i) {

		for(int j=1;j<=m;++j) {

			if(s[i][j]=='.') continue;

			if(a[i][j-1]) a[i][j]=a[i][j-1];

			else {

				a[i][j]=++js;

				dsr.push_back(js);

			}

			if(b[i-1][j]) b[i][j]=b[i-1][j];

			else {

				b[i][j]=++js;

				mmp.push_back(js);

			}

		}

	}

	S=501,T=502;

	for(iter i=dsr.begin();i!=dsr.end();++i) Add(S,*i,1);

	for(iter i=mmp.begin();i!=mmp.end();++i) Add(*i,T,1);

  	for(int i=1;i<=n;++i) {

		for(int j=1;j<=m;++j) {

			if(s[i][j]=='*') Add(a[i][j],b[i][j],1);

		}

	}

	printf("%d\n",dinic());

	return 0;

}

巴特西

bzoj 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场最小点覆盖

链接

思路

代码

最新文章

热门文章

巴特西

bzoj 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场 最小点覆盖

链接

思路

代码

最新文章

热门文章

bzoj 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场最小点覆盖