bzoj1735 [Usaco2005 jan]Muddy Fields 泥泞的牧场

传送门

分析

我们知道对于没有障碍的情况就是将横轴点于纵轴点连边

于是对于这种有障碍的情况我们还是分横轴纵轴考虑

只不过对于有障碍的一整条分为若干个无障碍小段来处理

然后将标号小段连边,跑最大匹配即可

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int n,m,be1[][],be2[][],g[][],Ans,T,used[],belong[];
char s[][];
inline bool work(int x){
for(int i=;i<=m;i++)
if(used[i]!=T&&g[x][i]){
used[i]=T;
if(!belong[i]||work(belong[i])){
belong[i]=x;
return ;
}
}
return ;
}
inline void go(){
for(int i=;i<=n;i++){
T=i;
if(work(i))Ans++;
}
}
int main(){
int w,r,i,j,k;
scanf("%d%d",&w,&r);
for(i=;i<w;i++)
scanf("%s",s[i]);
for(i=;i<w;i++){
k=;
for(j=;j<r;j++){
if(s[i][j]=='.'&&!k)k=;
if(s[i][j]=='*'){
if(k)n++,k=;
be1[i][j]=n;
}
}
}
for(i=;i<r;i++){
k=;
for(j=;j<w;j++){
if(s[j][i]=='.'&&!k)k=;
if(s[j][i]=='*'){
if(k)m++,k=;
be2[j][i]=m;
}
}
}
for(i=;i<w;i++)
for(j=;j<r;j++)
g[be1[i][j]][be2[i][j]]=;
go();
cout<<Ans;
return ;
}
上一篇:【转】C# 串口操作系列(1) -- 入门篇,一个标准的,简陋的串口例子。


下一篇:linux下web服务和部署Nginx