Hdu 5285 wyh2000 and pupil

发表于   |   分类于

官方题解
5285

Hdu 5285 wyh2000 and pupil

链接

wyh2000 and pupil

题意

有n个小学生，编号为1−n，要将所有小学生分成2组，每组都至少有1个人，
且每组中的小学生都互相认识。而且第一组的人要尽可能多，先给定m组关系
每组关系有两种个数 x,y(x<y)，表示x不认识y，y不认识x
求1,2组的认识分别为多少？如果找不到分组方案，则输出”Poor wyh”

分析

将不认识的学生连边，设任意一顶点为a,则与a关联的顶点不在同一组，
即若a在1组，那关联的点在2组，若a在2组，则关联的点在a组
由于存在多个不关联的集合，所以对于每个集合选取人数多的一组分为第1组
依次类推。。。
对于没有出现的顶点，表示他们之间互相认识，加到第一组即可
注：由于顶点数很多，邻接矩阵存不了，需要用到邻接表，
可以用vector数组存储，或者链式前向星解决

参考代码 (链式前向星)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<stdio.h>
#include<string.h>
#include<queue>
const int N=100000;
using namespace std;
struct stu
{
    int to;  //边的终点
    int next; //起点相同的下一条边
}edge[2*N+10];
int len,head[N+10],vis[N+10]; //head[i]为以i为起点的第一条边
bool flag[N+10];   //标记m组关系中出现的顶点
int n,m,one;
bool bfs()
{
    queue<int> q;
    one=0;    //one表示第一组的人数
    memset(vis,-1,sizeof(vis)); //vis为-1:未访问过，0：第1组，1:第2组
    for(int i=1; i<=n; i++){
        int cnt[2]={0}; 
        if(flag[i]&&vis[i]==-1){
            q.push(i);
            vis[i]=0;
            cnt[vis[i]]++;
        }
        while(!q.empty()){
            int top=q.front();
            q.pop();
            for(int j=head[top];j!=-1;j=edge[j].next){
                if(vis[edge[j].to]==-1){
                    cnt[!vis[top]]++;
                    q.push(edge[j].to);
                    vis[edge[j].to]=!vis[top];
                }
                else if(vis[top]==vis[edge[j].to])
                    return false;
            }
        }
        one+=max(cnt[0],cnt[1]);  //将人数多的分到第一组
    }
    return true;
}
void addEdge(int u,int v)
{
    edge[len].to=v;
    edge[len].next=head[u];
    head[u]=len++;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        if(n<2){  //每组至少1人
            printf("Poor wyh\n");
            continue;
        }
        memset(flag,false,sizeof(flag));
        memset(head,-1,sizeof(head));
        int num=0;
        len=0;
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            if(!flag[a]){
                num++;
                flag[a]=true;
            }
            if(!flag[b]){
                num++;
                flag[b]=true;
            }
            addEdge(a,b);
            addEdge(b,a);
        }
        if(bfs()){
            one+=n-num;
            if(one==n)  //每组至少一人
                one--;
            printf("%d %d\n",one,n-one);
        }
        else
            printf("Poor wyh\n");
    }
    return 0;
}

参考代码 (vector)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
const int N=100000;
using namespace std;
vector<int> edge[N+10];
int vis[N+10],n,m,one;
bool flag[N+10];
bool bfs()
{
    queue<int> q;
    one=0;
    memset(vis,-1,sizeof(vis));
    for(int i=1; i<=n; i++){
        int cnt[2]={0};
        if(flag[i]&&vis[i]==-1){
            q.push(i);
            vis[i]=0;
            cnt[vis[i]]++;
        }
        while(!q.empty()){
            int top=q.front();
            q.pop();
            int len=edge[top].size();
            for(int j=0;j<len;j++){
                int v=edge[top][j];
                if(vis[v]==-1){
                    cnt[vis[top]^1]++;
                    q.push(v);
                    vis[v]=vis[top]^1;
                }
                else if(vis[top]==vis[v])
                    return false;
            }
        }
        one+=max(cnt[0],cnt[1]);
    }
    return true;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        if(n<2){
            printf("Poor wyh\n");
            continue;
        }
        memset(flag,false,sizeof(flag));
        for(int i=1;i<=n;i++)
            edge[i].clear();
        int num=0;
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            if(!flag[a]){
                num++;
                flag[a]=true;
            }
            if(!flag[b]){
                num++;
                flag[b]=true;
            }
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
        if(bfs()){
            one+=n-num;
            if(one==n)
                one--;
            printf("%d %d\n",one,n-one);
        }
        else
            printf("Poor wyh\n");
    }
    return 0;
}

链式前向星简介

1
2
3
4
5
6
struct stu
{
    int next;
    int to;
    int w;
};

其中edge[i].to表示第i条边的终点,
edge[i].next表示与第i条边同起点的下一条边的存储位置,
edge[i].w为边权值.
head[i],它是用来表示以i为起点的第一条边存储的位置
head 数组一般初始化为-1
对于加边函数,len为当前要加的边的编号，可以初始化为0或1

1
2
3
4
5
6
7
void addEdge(int u,int v,int w)
{
    edge[len].to=v;
    edge[len].w=w;
    edge[len].next=head[u];
    head[u]=len++;
}

在遍历以顶点u为起点的所有边:

1
2
3
4
for(int i=head[u];i!=-1;i=edge[i].next){
    int v=edge[i].to;   //v为u的终点
    int w=edge[i].w;   //w为边权值
}