首页 > 代码库 > wyh2000 and pupil

wyh2000 and pupil

wyh2000 and pupil

 
 Accepts: 93
 
 Submissions: 925
 Time Limit: 3000/1500 MS (Java/Others)
 
 Memory Limit: 131072/65536 K (Java/Others)
问题描写叙述
青年理论计算机科学家wyh2000在教导他的小学生。
共同拥有个小学生,编号为。为了添加小学生之间的凝聚力,wyh2000决定将全部小学生分成组,每组都至少有个人。
可是有些小学生之间并不认识,并且假设不认识,那么也不认识

Wyh2000希望每组中的小学生都互相认识。并且第一组的人要尽可能多。 请你帮wyh2000求出第一组和第二组的人数是多少。假设找不到分组方案,则输出"Poor wyh"。

输入描写叙述
第一行一个数,表示数据组数。
对于每组数据,第一行两个数,表示小学生数量和互相不认识的小学生的数量。

接下来行,每行两个数,表示不认识不认识

保证一对仅仅会出现一次。

输出描写叙述
对于每组数据,输出答案。
输入例子
2
8 5
3 4
5 6
1 2
5 8
3 5
5 4
2 3
4 5
3 4
2 4
输出例子
5 3
Poor wyh
/*
Author: 2486
Memory: 7448 KB		Time: 592 MS
Language: G++		Result: Accepted
VJ RunId: 4055769		Real RunId: 14058285
Public:		No Yes
*/
/*
假设a不认识b,那么在a,b间连一条边,这样有解当且仅当这张图是二分图。
由于可能有多个二分图。而题目要求第一组的人尽可能多,所以贪心的选择就可以。

要注意m=0的情况。

*/ #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn=100000+5; vector<int>G[maxn]; int col[maxn],T; int n,m,a,b,acnt,bcnt; void init(int x) { for(int i=1; i<=x; i++) { G[i].clear(); } } bool bfs(int u) { queue<int>k; k.push(u); col[u]=1; while(!k.empty()) { int s=k.front(); if(col[s]==1)acnt++; else bcnt++; k.pop(); for(int i=0; i<G[s].size(); i++) { if(col[G[s][i]]==-1) { col[G[s][i]]=!col[s]; k.push(G[s][i]); continue; } if(col[G[s][i]]==col[s])return false; } } return true; } void slove() { memset(col,-1,sizeof(col)); bool flag=false; int Max=0; for(int i=1; i<=n; i++) { acnt=0,bcnt=0; if(col[i]==-1&&!bfs(i)) { flag=true; break; } Max+=max(acnt,bcnt);//必须这么做,由于这里面为1的或者为0的不一定就是同一阵营。

} if(flag)printf("Poor wyh\n"); else printf("%d %d\n",Max,n-Max); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); init(n); for(int i=0; i<m; i++) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } if(n<2) {//题目要求 printf("Poor wyh\n"); continue; } if(m==0) {//题目要求 printf("%d 1\n",n-1); continue; } slove(); } return 0; }



Statistic | Submit | Clarifications | Back

wyh2000 and pupil