/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://poj.org/problem?id=2724
Name : 2724 Purifying Machine
Date : Monday, December 19, 2011
Time Stage : one and half hour
Result:
9671768 panyanyany
2724
Accepted 4104K 391MS C++
2105B 2011-12-19 22:18:09
Test Data :
Review :
凡是涉及字符串处理的,肯定会出错……这题也逃不了这个怪圈。
一开始的时候不知道怎么判断是否只差一位,然后就找解题报告,
终于发现了一个巧妙的方法,感觉跟树状数组的 lowbit 差不多……
具体的分析请点击下列大牛的地址:
AekdyCoin的空间 http://hi.baidu.com/aekdycoin/blog/item/2dac891ea09ef9f2e1fe0b67.html
Uriel's Corner http://www.cppblog.com/Uriel/articles/122014.html
nizhenyang的博客 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 MAXSIZE 2002
int n, m, cnt ;
int seq[MAXSIZE], link[MAXSIZE] ;
bool cover[MAXSIZE] ;
bool graph[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 ()
{
int i, j ;
int a, b ;
int sum ;
char str[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 ;
}
分享到:
相关推荐
北大POJ1276试题代码
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
北大POJ1276-Cash Machine 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1745671
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
北大POJ初级-图算法 解题报告+AC代码
ACM POJ 解题报告北大POJ 大量解题代码
北大POJ初级题-数据结构:解题报告+AC代码
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ1159-Palindrome
北大POJ1837-Balance
poj openjudge 1111题最大正向匹配 提交ac
北大poj JAVA源码
北大POJ初级-所有题目AC代码+解题报告
北大POJ第1005题答案(C语言)
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ第1324题(C++)
北大POJ200多道程序解答 完整代码 供大家参考 相互切磋