Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 2724 Purifying Machine---二分图匹配

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;
}
 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理