|
|
Posted on 2010-08-02 22:42 Uriel 阅读(445) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 图论
建图啊建图。。 思路完全膜拜AC大牛的代码 http://hi.baidu.com/aekdycoin/blog/item/2dac891ea09ef9f2e1fe0b67.html.... 代码如下：
 //Problem: 2724 User: Uriel
//Memory: 384K Time: 110MS
//Language: G++ Result: Accepted
//floyd+Bipartite Graph
//2010.08.02
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n,m;
char a[1050][11];
int d[1050];
int nx,num[1050];
  int f[11]= {1,2,4,8,16,32,64,128,256,512,1024};
int link[1050],in[1050];
bool map(int a , int b){
 int t1=num[a],t2=num[b];
int m=t1^t2;
if(m && ((m&(m-1))==0))return true;
return false;
 }
bool fun(int k){
int i;
  for(i=0;i<nx;i++){
if(i==k)continue;
if(map(i,k) && !in[i]){
in[i]=1;
if(link[i]==-1 || fun(link[i])){
link[i]=k;
return true;
 }
}
}
return false;
}
int main(){
while(scanf("%d%d",&n,&m)){
if(n==0 && m==0)break;
nx=0;
int i,j,t;
memset(d,0,sizeof(d));
for(i=0;i<m;i++){
scanf("%s",(a[i]));
int flag=-1;
t=0;
for(j=0;j<n;j++){
if(a[i][j]=='*'){
flag=j;
continue;
}
t+=f[j]*(a[i][j]-'0');
}
if(!d[t]){
d[t]=1;
num[nx++]=t;
}
if(flag!=-1 && !d[t+f[flag]]){
d[t+f[flag]]=1;
num[nx++]=t+f[flag];
}
}
int res=0;
memset(link,-1,sizeof(link));
for(i=0;i<nx;i++){
memset(in,0,sizeof(in));
if(fun(i))res++;
}
printf("%d\n",nx-res/2);
}
return 0;
}
|