【二分图+最大匹配】北大 poj 2724 Purifying Machine
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL : http://poj.org/problem?id=2724Name : 2724 Purifying MachineDate : Monday, December 19, 2011Time Stage : one and half hourResult: 9671768panyanyany2724Accepted4104K391MSC++2105B2011-12-19 22:18:09Test Data :Review :凡是涉及字符串处理的，肯定会出错……这题也逃不了这个怪圈。一开始的时候不知道怎么判断是否只差一位，然后就找解题报告，终于发现了一个巧妙的方法，感觉跟树状数组的 lowbit 差不多……具体的分析请点击下列大牛的地址：AekdyCoin的空间 http://hi.baidu.com/aekdycoin/blog/item/2dac891ea09ef9f2e1fe0b67.htmlUriel's Corner http://www.cppblog.com/Uriel/articles/122014.htmlnizhenyang的博客 http://blog.sina.com.cn/s/blog_6a98ae6c0100nflu.html月拌西凉的空间 http://hi.baidu.com/%D4%C2%B0%E8%CE%F7%C1%B9/blog/item/6eb3893752e50f4ead4b5ff2.html//----------------------------------------*/#include <stdio.h>#include <string.h>#define MAXSIZE2002intn, m, cnt ;intseq[MAXSIZE], link[MAXSIZE] ;boolcover[MAXSIZE] ;boolgraph[MAXSIZE][MAXSIZE] ;void cnvToDig (char *str, int *a, int *b){int i, starPos ;*a = *b = 0 ;starPos = -1 ;for (i = 0 ; i < strlen (str) ; ++i){if (str[i] == '*'){starPos = (n - i - 1) ;}else if (str[i] == '1'){*a |= 1 << (n - i - 1) ;}}*b = (starPos == -1) ? (*a) : (*a | (1 << starPos)) ;}inline bool onlyDiff (int lhs, int rhs){int c = lhs ^ rhs ;return c && !(c & (c-1)) ;}bool noRepeat (int a){int i ;for (i = 0 ; i < cnt ; ++i)if (seq[i] == a)return false ;return true ;}bool find (int cur){int i, j ;for (i = 0 ; i < cnt ; ++i){if (!cover[i] && graph[cur][i]){cover[i] = true ;if (link[i] == -1 || find (link[i])){link[i] = cur ;return true ;}}}return false ;}int main (){inti, j ;inta, b ;intsum ;charstr[20] ;while (scanf ("%d%d", &n, &m), n | m){getchar () ;for (i = cnt = 0 ; i < m ; ++i){gets (str) ;cnvToDig (str, &a, &b) ;//printf ("%d, %d\n",a , b) ;if (noRepeat(a))seq[cnt++] = a ;if (a != b && noRepeat (b))seq[cnt++] = b ;}memset (graph, false, sizeof (graph)) ;for (i = 0 ; i < cnt ; ++i)for (j = i + 1 ; j < cnt ; ++j)if (onlyDiff(seq[i], seq[j]))graph[i][j] = graph[j][i] = true ;sum = 0 ;memset (link, -1, sizeof (link)) ;for (i = 0 ; i < cnt ; ++i){memset (cover, 0, sizeof (cover)) ;sum += find (i) ;}printf ("%d\n", cnt - sum / 2) ;}return 0 ;}?