博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 5285 wyh2000 and pupil(dfs或种类并查集)
阅读量:5876 次
发布时间:2019-06-19

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

wyh2000 and pupil

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 755    Accepted Submission(s): 251
Problem Description
Young theoretical computer scientist wyh2000 is teaching his pupils.
Wyh2000 has n pupils.Id of them are from
1 to
n.In order to increase the cohesion between pupils,wyh2000 decide to divide them into 2 groups.Each group has at least 1 pupil.
Now that some pupils don't know each other(if
a doesn't know
b,then
b doesn't know
a).Wyh2000 hopes that if two pupils are in the same group,then they know each other,and the pupils of the first group must be as much as possible.
Please help wyh2000 determine the pupils of first group and second group. If there is no solution, print "Poor wyh".
 
Input
In the first line, there is an integer
T indicates the number of test cases.
For each case, the first line contains two integers
n,m indicate the number of pupil and the number of pupils don't konw each other.
In the next m lines,each line contains 2 intergers
x,y(x<
y),indicates that
x don't know
y and
y don't know
x,the pair
(x,y) will only appear once.
T10,0n,m100000
 
Output
For each case, output the answer.
 
Sample Input
 
2 8 5 3 4 5 6 1 2 5 8 3 5 5 4 2 3 4 5 3 4 2 4
 
Sample Output
 
5 3 Poor wyh
 
大致题意:
n个点分成两组,m条边,每条边连接的两个点必须是在不同的两组,且第一组要尽量的大
思路:显然。dfs染色,不是二分图就无解。
还能够用种类并查集来做,把全部可能性合并,由对称性可知,仅仅统计1~n是祖先时。看祖先的子节点中黑白节点是多少个就ok
//468MS 4036K 1981 B C++  #include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define SZ(x) ((int)(x).size())#define ALL(v) (v).begin(), (v).end()#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)#define REP(i,n) for ( int i=1; i<=int(n); i++ )using namespace std;typedef long long ll;#define X first#define Y secondtypedef pair
pii;const int N = 1e5+100;int sz[N*2];int sz2[N*2];int fa[N*2];int n,m;void ini(){ REP(i,2*n) fa[i] = i; REP(i,2*n) sz[i] = (i <= n); REP(i,2*n) sz2[i] = (i > n);}int getf(int x){ return x == fa[x] ? x : fa[x] = getf(fa[x]);}bool same(int a,int b){ return getf(a) == getf(b);}void Merge(int a,int b){ int f1 = getf(a), f2 = getf(b); if(f1 == f2) return ; fa[f1] = f2; sz[f2] += sz[f1]; sz2[f2] += sz2[f1];}int main(){ int T; cin>>T; while(T--){ scanf("%d%d",&n,&m); ini(); bool flag = 0; REP(i,m){ int a,b; scanf("%d%d",&a,&b); if(flag) continue; if(same(a,b) || same(a+n,b+n) ) flag = 1; else Merge(a+n,b),Merge(a,b+n); } if( n < 2 || flag) puts("Poor wyh"); else if(m == 0) printf("%d 1\n",n-1); else { int ans = 0; REP(i,n){ if( fa[i] == i) ans += min(sz[i],sz2[i]); } printf("%d %d\n",n-ans,ans); } }}

转载地址:http://tzkix.baihongyu.com/

你可能感兴趣的文章
nginx 配置ssl实现https
查看>>
APP消息推送:通知和透传
查看>>
通过Gradle Plugin实现Git Hooks检测机制
查看>>
css里那些可以继承的属性
查看>>
卖人参
查看>>
react, webpack4,json-server, 模拟前端数据(POST+自定义数据)
查看>>
JVM系列(二):深入讲解JVM内存溢出分析!
查看>>
讯飞开放平台开春福利:17种方言全配齐 让你的AI“语种”不同
查看>>
JavaScript 异步编程之回调函数
查看>>
TypeSprict -- 接口
查看>>
《重构 - 改善既有代码的设计》
查看>>
虹软人脸识别 - ArcFace SDK介绍及使用注意事项
查看>>
倒排索引创建案例
查看>>
Firewalld的概念与使用
查看>>
React项目技术栈
查看>>
项目线程安全
查看>>
java B2B2C源码电子商务平台-配置中心svn示例和refresh
查看>>
数据分析Power BI数据建模教程(二)——如何创建计算列
查看>>
Kuuga——转化任何 Web 页面为桌面应用的跨平台工具
查看>>
Java11都出来了还要学Java8新特性吗?
查看>>