/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://poj.org/problem?id=2771
Name : 2771 Guardian of Decency
Date : Monday, November 21, 2011
Time Stage : one hour and a half
Result:
9585300 panyanyany
2771
Accepted 524K 2391MS C++
2084B 2011-11-21 21:10:58
Test Data :
Review :
一开始以为是最大匹配,就是可以去的同学两两匹配,然后找最大的匹配……
看了人家的代码才知道,原来是求所谓的最大独立集,要匹配会发生感情的同学
然后用总数减去这些同学,就是完全不会谈恋爱的同学了,然后再把那些会恋爱的同学两两拆散,
加到完全不会恋爱的同学中,就是最大独立集了。感觉这招够毒的……
用时花了2千多毫秒,不知道人家7十多的怎么实现的……
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <math.h>
using std::vector ;
#define MAXSIZE 508
int tcase, n ;
int link[MAXSIZE], cover[MAXSIZE] ;
bool map[MAXSIZE][MAXSIZE] ;
struct characteristic {
int age ;
char sex ;
char music_style[101] ;
char fav_sport[101] ;
bool IsCouple (characteristic other)
{
if ((abs (age - other.age) > 40) ||
(sex == other.sex) ||
(strcmp (music_style, other.music_style)) ||
(!strcmp (fav_sport, other.fav_sport)))
return false ;
else
return true ;
}
};
characteristic pupils[MAXSIZE] ;
bool find (int cur)
{
int i, j ;
for (i = 1 ; i <= n ; ++i)
{
if (cover[i] == false && map[cur][i] == true)
{
cover[i] = true ;
if (link[i] == 0 || find (link[i]))
{
link[i] = cur ;
return true ;
}
}
}
return false ;
}
int main ()
{
int i, j ;
int sum ;
while (~scanf ("%d", &tcase))
{
while (tcase--)
{
scanf ("%d", &n) ;
for (i = 1 ; i <= n ; ++i)
{
scanf ("%d %c %s %s", &pupils[i].age, &pupils[i].sex,
pupils[i].music_style, pupils[i].fav_sport) ;
// printf ("[%d], [%c], [%s], [%s]\n", pupils[i].age, pupils[i].sex,
// pupils[i].music_style, pupils[i].fav_sport) ;
}
memset (map, 0, sizeof (map)) ;
for (i = 1 ; i <= n ; ++i)
{
for (j = 1 ; j <= n ; ++j)
{
map[i][j] = pupils[i].IsCouple (pupils[j]) ;
// printf ("%d ", map[i][j]) ;
}
// puts ("") ;
}
sum = 0 ;
memset (link, 0, sizeof (link)) ;
for (i = 1 ; i <= n ; ++i)
{
memset (cover, 0, sizeof (cover)) ;
sum += find (i) ;
}
printf ("%d\n", n - sum/2) ;
}
}
return 0 ;
}
分享到:
相关推荐
poj 2771 Guardian of Decency.md
北大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,...
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
北大POJ初级-图算法 解题报告+AC代码
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
ACM POJ 解题报告北大POJ 大量解题代码
北大POJ初级题-数据结构:解题报告+AC代码
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ1159-Palindrome
北大POJ1837-Balance
北大poj JAVA源码
北大POJ初级-所有题目AC代码+解题报告
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ第1005题答案(C语言)
北大POJ第1324题(C++)
NULL 博文链接:https://128kj.iteye.com/blog/1772172
北大POJ200多道程序解答 完整代码 供大家参考 相互切磋
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习