首页 > 代码库 > wyh2000 and pupil
wyh2000 and pupil
wyh2000 and pupil
青年理论计算机科学家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; }
wyh2000 and pupil