hdu5285 wyh2000 and pupil

本文主要是介绍hdu5285 wyh2000 and pupil，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对图染色，如果相邻的边染色一样，那么说明错误，输出那个不可能的字符串

否则输出最大的那组人数个最小的那组人数

特判：m ==0  和  最大那组人数为 n的时候

注意：杭电后台使用的是windows，会爆栈

最好用一下：#pragma comment(linker, "/STACK:1024000000,1024000000") 

具体解释请看这篇文章  http://bbs.byr.cn/#!article/ACM_ICPC/51264

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define N 111111
int T;
int vis[N];
int v[N];
int d[N];
vector<int>g[N];
int flag;
int n,m;
int cnt1,cnt2;
void dfs(int u,int val){d[u]=val;if(val==1) cnt1++;else cnt2++;//printf("%d %d\n",u,val);int k = g[u].size();for(int i=0;i<k;i++){int vv = g[u][i];if(!v[vv]){v[vv]=1;dfs(vv,val^1);}else{if(d[u]==d[vv]){flag = 0;return ;}}}
}int main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){g[i].clear();}memset(d,-1,sizeof(d));memset(vis,0,sizeof(vis));memset(v,0,sizeof(v));while(m--){int x,y;scanf("%d%d",&x,&y);g[x].push_back(y);g[y].push_back(x);vis[x]=1;vis[y]=1;}if(n==1||n==0) {printf("Poor wyh\n");continue;}flag =1;int ans = 0;int ans1=0;int ans2=0;for(int i=1;i<=n;i++){if(vis[i]&&!v[i]){cnt1=0;cnt2=0;v[i]=1;dfs(i,1);ans1+=max(cnt1,cnt2);ans2+=min(cnt1,cnt2);}if(!vis[i]){ans++;}}// printf("----%d %d\n",ans1,ans2);if(flag){if(max(ans1,ans2)+ans==n){printf("%d 1\n",n-1);}else{printf("%d %d\n",max(ans1,ans2)+ans,min(ans1,ans2));}}elseputs("Poor wyh");}
}

这篇关于hdu5285 wyh2000 and pupil的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---