|
Posted on 2010-08-02 22:42 Uriel 阅读(440) 评论(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; }
|