这是我做过的第一道，第一道二分图最小点集覆盖问题，其实我也不清楚是不是叫这个= =|||
上题目：
Description
Rain has pummeled the cows' field
, a rectangular grid of R rows and C columns (1 <= R <= 50, 1 <= C <= 50). While good for the grass, the rain makes some patches of bare earth quite muddy. The cows, being meticulous grazers, don't want to get their hooves dirty while they eat.
To prevent those muddy hooves, Farmer John will place a number of wooden boards over the muddy parts of the cows' field. Each of the boards is 1 unit wide, and can be any length long. Each board must be aligned parallel to one of the sides of the field.
Farmer John wishes to minimize the number of boards needed to cover the muddy spots, some of which might require more than one board to cover. The boards may not cover any grass and deprive the cows of grazing area but they can overlap each other.
Compute the minimum number of boards FJ requires to cover all the mud in the field.
Input
* Line 1: Two space-separated integers: R and C
* Lines 2..R+1: Each line contains a string of C characters, with '*' representing a muddy patch, and '.' representing a grassy patch. No spaces are present.
Output
* Line 1: A single integer representing the number of boards FJ needs.
Sample Input
4 4
*.*.
.***
***.
..*.
Sample Output
4
Hint
OUTPUT DETAILS:
Boards 1, 2, 3 and 4 are placed as follows:
1.2.
.333
444.
..2.
Board 2 overlaps boards 3 and 4.
题目意思很清楚，差不多就是R*C的矩阵里，有些格子有‘*’，你要用最少的木板，将这些‘*'都覆盖，且不能覆盖‘.’。
这题很容易会走错方向 ， 会走到哪呢，我也不知道o o
这题tmd要怎么构图，如果木板长度为2的话就水了，说实话我被如何构图给难住了。。1个小时过去了，总算是有点眉目了0 0
这题的构图就是丧心病狂，先横的来，就拿样例来说，（1,1）∈ x子集的第一个点，（1,3）∈第二个点，（2,2）∈第三个，（2,3）∈第3个……然后y子集便是竖的来一遍，‘ * ’就表示 x子集与y子集连边0 0
哈♂ 哈♂ 哈♂ 哈♂ 图居然被我构出来了
然后就简单了，跑一遍匈牙利即可，具体可看代码
#include<cstdio>
#include<cstring>
using namespace std;
int f[500][500],y[500],link[500],hang,lie,n,m,k,x,z;
char a[51][51];bool b;
int mapl[500][500],mapr[500][500];
bool find(int v){
for(int i=1;i<=f[v][0];i++){
int j=f[v][i];
if(!y[j]){
y[j]=1;
if(!link[j]||find(link[j])){
link[j]=v;
return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);getchar();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
scanf("%c",&a[i][j]);
getchar();
}++hang;++lie;b=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='*'){
b=1;
mapl[i][j]=hang;
}else if(b){
b=0;
++hang;
}
}
if(b)++hang;
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(a[i][j]=='*'){
b=1;
mapr[i][j]=lie;
}else if(b){
b=0;
++lie;
}
}
if(b)++lie;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i][j]=='*')f[mapl[i][j]][++f[mapl[i][j]][0]]=mapr[i][j];
}
memset(link,0,sizeof(link));
int ans=0;
for(int i=1;i<=hang;i++){
memset(y,0,sizeof(y));
if(find(i))++ans;
}
printf("%d\n",ans);
}
loading...
评论 (0)
