随笔-72  评论-126  文章-0  trackbacks-0
http://acm.pku.edu.cn/JudgeOnline/problem?id=2724
 1 #include<stdio.h>
 2 #include<string.h>
 3 #define M 1024
 4 int chess[M];
 5 int hh[M][M];
 6 int link[M];
 7 char visit[M];
 8 char num[M];
 9 int to_10(char *a)
10 {
11     int n=0;
12     for(;*a;a++)
13         n = n*2 + (*a)-'0';
14     return n;
15 }
16 int pipei(int n)
17 {
18     return (n&&((n&(n-1))==0));
19 }
20 int find(int a,int m)
21 {
22     int b;
23     for(b=0;b<m;b++)
24     {
25         if(hh[a][b]&&!visit[b])
26         {
27             visit[b]=1;
28             if(link[b]==-1||find(link[b],m)) 
29             {
30                 link[b] = a;
31                 return 1;
32             }
33         }
34     }
35     return 0;
36 }
37 int main()
38 {
39     int n,m,i,k,a,b,max,count;
40     char str1[100],str2[100];
41     while (scanf("%d%d%",&n,&m),n+m)
42     {
43         k = 0;
44         memset(num,0,sizeof(num));
45         while(m--)
46         {
47             scanf("%s",str1);
48             for(i=0;str1[i];i++)
49                 if(str1[i]=='*')
50                     break;
51                 if(str1[i])
52                 {
53                     strcpy(str2,str1);
54                     str1[i] = '0';
55                     str2[i] = '1';
56                     num[to_10(str1)] = 1;
57                     num[to_10(str2)] = 1;
58                 }
59                 else
60                     num[to_10(str1)] = 1;
61         }
62         max = 1<<n;
63         for(i=0;i<max;i++)
64             if(num[i])
65                 chess[k++]=i;
66         for(a=0;a<k;a++)
67         {
68             for(b=0;b<k;b++)
69             {
70                 if(a==b)
71                     continue;
72                 hh[a][b] = pipei(chess[a]^chess[b]);
73             }
74         }
75         memset(link,-1,sizeof(link));
76         count = 0;
77         for(i=0;i<k;i++)
78         {
79             memset(visit,0,sizeof(visit));
80             count += find(i,k);
81         }
82         printf("%d\n",k-count/2);
83     }
84     return 0;
85 }
86 
87 

 二分模板http://acm.hdu.edu.cn/showproblem.php?pid=2119
#include<stdio.h>
#include
<string>
#define M 101
int map[M][M];
int visit[M];
int link[M];
int n,m;
int find(int a)
{
    
int b;
    
for(b=0;b<m;b++)
    {
        
if(map[a][b] && !visit[b])
        {
            visit[b] 
= 1;
            
if(link[b]==-1 || find(link[b]))
            {
                link[b] 
= a;
                
return 1;
            }
        }
    }
    
return 0;
}
int match()
{
    
int sum=0,i;
    memset(link,
-1,sizeof(link));
    
for(i=0;i<n;i++)
    {
        memset(visit,
0,sizeof(visit));
        sum 
+= find(i);
    }
    
return sum;
}
int main()
{
    
int i,j;
    
while(scanf("%d",&n),n)
    {
        scanf(
"%d",&m);
        
for(i=0;i<n;i++)
            
for(j=0;j<m;j++)
                scanf(
"%d",&map[i][j]);
        printf(
"%d\n",match());
    }
    
return 0;
}

posted on 2009-02-09 22:43 shǎ崽 阅读(333) 评论(0)  编辑 收藏 引用

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