博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ2744:[HEOI2012]朋友圈(最大团,乱搞)
阅读量:6113 次
发布时间:2019-06-21

本文共 1890 字,大约阅读时间需要 6 分钟。

Description

在很久很久以前,曾经有两个国家和睦相处,无忧无虑的生活着。一年一度的评比大会开始了,作为和平的两国,一个朋友圈数量最多的永远都是最值得他人的尊敬,所以现在就是需要你求朋友圈的最大数目。
两个国家看成是AB两国,现在是两个国家的描述:
1. A国:每个人都有一个友善值,当两个A国人的友善值a、b,如果a xor b mod 2=1,
那么这两个人都是朋友,否则不是;
2.B国:每个人都有一个友善值,当两个B国人的友善值a、b,如果a xor b mod 2=0
或者 (a or b)化成二进制有奇数个1,那么两个人是朋友,否则不是朋友;
3. A、B两国之间的人也有可能是朋友,数据中将会给出A、B之间“朋友”的情况。
4.在
AB两国,朋友圈的定义:一个朋友圈集合
S,满足

S∈A∪ B,对于所有的i,j∈S,i和j是朋友

由于落后的古代,没有电脑这个也就成了每年最大的难题,而你能帮他们求出最大朋友圈的人数吗?

Input

第一行t<=6,表示输入数据总数。
接下来t个数据:
第一行输入三个整数A,B,M,表示A国人数、B国人数、AB两国之间是朋友的对数;第二行A个数ai,表示A国第i个人的友善值;第三行B个数bi,表示B国第j个人的友善值;
第4——3+M行,每行两个整数(i,j),表示第i个A国人和第j个B国人是朋友。

Output

输出t行,每行,输出一个整数,表示最大朋友圈的数目。

Sample Input

2 4 7
1 2
2 6 5 4
1 1
1 2
1 3
2 1
2 2
2 3
2 4

Sample Output

5
【样例说明】
最大朋友圈包含A国第1、2人和B国第1、2、3人。

HINT

【数据范围】

两类数据
第一类:|A|<=200 |B| <= 200
第二类:|A| <= 10 |B| <= 3000

Solution

$A$了这个题才发现这个题网上怎么清一色匈牙利……QAQ。来一发应该是对的乱搞做法。

定义权值为奇数的为奇点,偶数的为偶点。首先简单分析一下$A,B$国的性质,可以发现:

$A$国内的边只有奇点连向偶点,也就是说只看$A$国的话是一个奇-偶的完全二分图。且若答案最大团里含$A$国的人,则奇点最多只有一个,偶点最多只有一个。(因为如果选两个奇点的话这两个奇点中间必定没有边,偶点同理。)

$B$国内奇点成一个团,偶点成一个团,且$(b_i~or~b_j)$化成二进制有奇数个$1$的也互连。也就是两个团之间连着几条边的形态。

分析完性质,可以发现$B$国的两个团并不一定是极大团,因为如果两个团之间连着的边足够的话,奇点也是可以被并到偶团里的。那么我们暴力一下,把$B$国的两个团都扩成极大团。

因为$A$国只有可能被选$0,1,2$个点去和$B$国的两个极大团合并,枚举一下$A$国选哪些就好了。

注意一些边界条件,具体看代码。

Code

1 #include
2 #include
3 #include
4 #include
5 #define N (3009) 6 using namespace std; 7 8 int n,m,x,y,u,v,ans; 9 int a[N],b[N],G[N][N];10 vector
A[2],B[2];11 12 inline int read()13 {14 int x=0,w=1; char c=getchar();15 while (!isdigit(c)) {
if (c=='-') w=-1; c=getchar();}16 while (isdigit(c)) x=x*10+c-'0', c=getchar();17 return x*w;18 }19 20 int bitcount(int x)21 {22 return x?bitcount(x>>1)+(x&1):0;23 }24 25 bool check(int x,int opt)26 {27 bool flag=1;28 for (int i=0; i

转载于:https://www.cnblogs.com/refun/p/10438009.html

你可能感兴趣的文章
bulk
查看>>
js document.activeElement 获得焦点的元素
查看>>
C++ 迭代器运算
查看>>
【支持iOS11】UITableView左滑删除自定义 - 实现多选项并使用自定义图片
查看>>
day6-if,while,for的快速掌握
查看>>
JavaWeb学习笔记(十四)--JSP语法
查看>>
【算法笔记】多线程斐波那契数列
查看>>
java8函数式编程实例
查看>>
jqgrid滚动条宽度/列显示不全问题
查看>>
在mac OS10.10下安装 cocoapods遇到的一些问题
查看>>
angularjs表达式中的HTML内容,如何不转义,直接表现为html元素
查看>>
css技巧
查看>>
Tyvj 1728 普通平衡树
查看>>
[Usaco2015 dec]Max Flow
查看>>
javascript性能优化
查看>>
多路归并排序之败者树
查看>>
java连接MySql数据库
查看>>
转:Vue keep-alive实践总结
查看>>
android studio修改新项目package名称
查看>>
深入python的set和dict
查看>>