POJ3020【最大匹配】
原题描述：
见原题
题目大意：
给出一张图，图中元素为’*'或者’o'。其中，相连的两个’*’可以划入一个圈中。问至少需要几个圈将所有的’*'画起来。
解题思路：
若两个点都为’*'且相连，则这两个点间有边。图中每个点化ij化为新点 i*w + j（以表示出所有点）。于是，最大匹配问题就明朗了。
代码：
#include <stdio.h>
#include <string.h>
#define MAXN 410
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
int hungary(int m,int n,int mat[][MAXN],int* match1,int* match2){
int s[MAXN],t[MAXN],p,q,ret=0,i,j,k;
for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j<n&&match1[i]<0;j++)
if (mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
return ret;
}
int main(int argc, char *argv[]){
int iTest;
scanf(“%d”,&iTest);
int map_ap[410][410];
while(iTest–){
int h,w;
scanf(“%d %d”,&h,&w);
int i,k;
int map_in[40][10];
int n = 0;
for(i = 0; i < h * w; ++i){
for(k = 0; k < h * w; ++k){
map_ap[i][k] = 0;
}
}
for(i = 0; i < h; ++i){
char sentense_in[12];
scanf(“%s”,&sentense_in);
for(k = 0; k < w; ++k){
if(‘o’ == sentense_in[k]){
map_in[i][k] = 0;
}else if(‘*’ == sentense_in[k]){
map_in[i][k] = 1;
n++;
if(i){
if(map_in[i - 1][k]){
map_ap[i * w + k][(i - 1) * w + k] = 1;
map_ap[(i - 1) * w + k][i * w + k] = 1;
}
}
if(k){
if(map_in[i][k - 1]){
map_ap[i * w + k][i * w + k - 1] = 1;
map_ap[i * w + k - 1][i * w + k] = 1;
}
}
}else{
k–;
}
}
}
int m1[410],m2[410];
printf(“%d\n”,n – hungary(h * w,h * w,map_ap,m1,m2) / 2);
}
return 0;
}