hdu 5285 wyh2000 and pupil (交叉染色法,二分图点集差最大)

题目链接:hdu 5285 题目lianjie

题意:给定n个小朋友,以及小朋友之间的关系,要求将小朋友分成两组,**并且每组至少一个人,**现在问能否这样分组,如果有解,输出两组的人数,并保证第一组的人数尽可能地大。

思路:。。。一开始看到n的数据范围。。。想当然的以为会给认识的人的关系。。。尼玛。。。求个补图就够受的了。。。。不会做,卒。

结果发现。。竟然给的是两个人不认识的关系。。。2333

那么我们来交叉染色。。。

实际上交叉染色的过程中,颜色相同的点属于二分图中相同的点集合。

交叉染色其实是在模拟交错轨的过程...?

由于图不一定联通,可能由多个联通块。

我们在交叉染色的时候记录一下0,1的个数(也就是两个点集的大小)

然后每次把大的累加(因为没说不认识的就是默认认识了。。。)

无解的情况有:任何一个联通快无解或者n<=1

此外还需要注意,m可能为0.

特判一下,m为0或者为1,直接输出n-1和1.

以及!

n<=1的无解是在特判m之前的。。。。我好傻啊。

n<=1的无解是在特判m之前的。。。。我好傻啊。

n<=1的无解是在特判m之前的。。。。我好傻啊。

/* ***********************************************
Author :111qqz
Created Time :2016年09月02日 星期五 14时41分35秒
File Name :code/hdu/5285.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int M = 2E5+7;
const int N = 1E5+7;
int n,m;
int head[N];
int col[N];
struct Edge
{
    int v;
    int nxt;
}edge[M];
int cnt;
int cnt0,cnt1;
void addedge(int u ,int v)
{
    edge[cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
    cnt++;
}
int dfs( int u,int x,int fa)
{
    col[u] = x;
    if (x==0) cnt0++;else cnt1++;
    for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
    {
	int v = edge[i].v;
	if (v==fa) continue;
	if (col[v]==1-x) continue;
	if (col[v]==x) return -1;
	if (!dfs(v,1-x,u)) return -1;
    }
    return max(cnt0,cnt1);
}
int  solve()
{
    int res = 0  ;
    for ( int i = 1 ; i <= n ; i++)
    {
	if (col[i]!=-1) continue;
	cnt0 = cnt1 = 0 ;
	int tmp = dfs(i,0,-1);
	if (tmp==-1) return -1;
	res+=tmp;
    }
    return res;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	int T;
	cin>>T;
	while (T--)
	{
	    scanf("%d%d",&n,&m);
	    cnt = 0 ;
	    ms(head,-1);
	    ms(col,-1);
	    for ( int i = 1 ; i <= m ; i++)
	    {
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v);
		addedge(v,u);
	    }
	    if (n<2)
	    {
		puts("Poor wyh");
		continue;
	    }
	    if (m<=1)
	    {
		printf("%d %d\n",n-1,1);
		continue;
	    }
	    int ans = solve();
	    if (ans==-1) puts("Poor wyh");
	    else printf("%d %d\n",ans,n-ans);
	}
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}