rt

P6062 [USACO05JAN]Muddy Fields G

24 分 #2等 WA 样例已过

#include<bits/stdc++.h>
using namespace std;
const int maxn=52*52,inf=1e5;
int cnt=0,tot=0,n,m,cnt1,cnt2,en,p[inf*100],head[inf*100];
bool vis[inf*100],f[52][52];
pair<int,int> pic[maxn],a[maxn];
struct edge{
	int nxt,to;
}e[maxn];
void add(int x,int y){
	e[++cnt]={head[x],y};
	head[x]=cnt;
}
bool dfs(int x){
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(!vis[to]){
			vis[to]=1;
			if(p[to]==0||dfs(p[to])){
				p[to]=x;
				return 1;
			}
		}
	}
	return 0;
}
int Hungarian(){
	int res=0;
	memset(p,0,sizeof(p));
	for(int i=1;i<=cnt2;i++){
		memset(vis,0,sizeof(vis));
		res+=dfs(i);
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		string s1;
		cin>>s1;
		for(int j=1;j<=m;j++){
			if(s1[j-1]=='*')	pic[++tot]=make_pair(i,j),f[i][j]=1;
		}
	}
	for(int i=1;i<=tot;i++){
		// printf("**%d\n",pic[i].second);
		if(pic[i].first==1||!f[pic[i].first-1][pic[i].second]){
			a[i].first=++cnt1;
		}
		else	a[i].first=cnt1;
	}
	for(int i=1;i<=tot;i++){
		if(pic[i].second==1||!f[pic[i].first][pic[i].second-1]){
			a[i].second=++cnt2;
		}
		else	a[i].second=cnt2;
		// printf("%d %d\n",pic[i].first+more,pic[i].second-m);
	}
	for(int i=1;i<=tot;i++){
		add(a[i].first,a[i].second+cnt1);
		add(a[i].second+cnt1,a[i].first);
		// printf("%d %d\n",pic[i].first,pic[i].second);
	}
	printf("%d",Hungarian());
}

#2

30 30
..............................
..............................
..............................
..............................
..............................
..........**************......
..........*............*......
..........*............*......
..........*..*..****...*......
..........*..*.....*...*......
..........*..*...****..*......
..........*..*.....*...*......
..........*..*.....*...*......
..........*............*......
..........*............*......
..........**************......
..........*...................
..........*...................
..........*...................
..........*...................
...*......*...................
...*......*...................
...*......*...................
...*......*...................
...*......*...................
...*......*...................
...********...................
..............................
..............................
..............................

悬赏两个关注