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ǎ崽 閱讀(338)
評論(0) 編輯 收藏 引用