首页 > ACM题库 > HDU-杭电 > hdu 1941 Justice League[解题报告]C++
2013
12-26

hdu 1941 Justice League[解题报告]C++

Justice League

问题描述 :

Thirty five years ago, a group of super heroes was chosen to form the Justice League, whose purpose was to protect the planet Earth from the villains. After all those years helping mankind, its members are retiring and now it is time to choose the new members of the Justice League. In order to keep their secret identity, let’s say, secret, super heroes usually use an integer number to identify themselves. There are H super heroes on Earth, identified with the integers from 1 to H. With a brief look at the newspapers anyone can find out if two super heroes have already worked together in a mission. If this happened, we say that the two heroes have a relationship.

There must be only one Justice League in the world, which could be formed by any number of super heroes (even only one). Moreover, for any two heroes in the new league, they must have a relationship.

Besides, consider the set of the heroes not chosen to take part in the Justice League. For any two heroes on that set, they must not have a relationship. This prevents the formation of unofficial justice leagues.

You work for an agency in charge of creating the new Justice League. The agency doesn’t know if it is possible to create the League with the restrictions given, and asked for your programming skills. Given a set of super heroes and their relationships, determine if it is possible to select any subset to form the Justice League, according to the given restrictions.

输入:

The input is composed of several test cases. The first line of each test case contains two integers separated by a single space, H (2 <= H <= 5×104) and R (1 <= R <= 105), indicating, respectively, the number of heroes and the number of relationships. Each of the following R lines contains two integers separated by a single space, A and B (1 <= A < B <= H), indicating that super hero A has a relationship with super hero B. Note that if A has a relationship with B, B also has a relationship with A. A relationship is never informed twice on a test case.
The end of input is indicated by H = R = 0.

输出:

The input is composed of several test cases. The first line of each test case contains two integers separated by a single space, H (2 <= H <= 5×104) and R (1 <= R <= 105), indicating, respectively, the number of heroes and the number of relationships. Each of the following R lines contains two integers separated by a single space, A and B (1 <= A < B <= H), indicating that super hero A has a relationship with super hero B. Note that if A has a relationship with B, B also has a relationship with A. A relationship is never informed twice on a test case.
The end of input is indicated by H = R = 0.

样例输入:

5 5
1 2
2 3
1 3
1 4
3 5
9 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
4 3
1 2
2 3
3 4
0 0

样例输出:

Y
N
Y

HDU_1941

    这个题目说白了就是要删掉一些点,而且被删掉的点两两之间不能有边,留下的点两两之间必须有边,也就是构成一个完全图。

    乍看起来是没啥思路的,不过大概有两条路子可以走,要么先考虑什么样的点一定会留下来,要么就先考虑什么样的点一定会被删掉。想想之后觉得第二条路子还可行一些,于是就开始想吧。

    首先,孤立点是一定可以被删除的(这里以及后面的讨论默认最大度数的点的度数还算比较大),其次好像叶子节点也就是度数为1的点也可以删,再接着好像就不太好讨论了,不过前面这两类点是有共性的,也就是度数比较小,那么是不是先把度数比较小的点删掉就可以了?

    不妨考虑一个度数比较小的点A和一个度数比较大的点B,根据两个点集合的从属关系无非有4种情况:①A和B都被删掉了;②A删掉了,B留下;③A留下,B删掉了,不过这种情况是不可以的,因为假设A是完全图中的点,由于B的度数比A大,即便它和完全图中的所有点都有边,那么还是会有多余的度数,所以一定会和删掉的点之间形成边,所以这种情况不可能发生;④A和B都留下了,这也不可能,因为A的度数比B小,不可能和B一起组成完全图。分析完这四种情况就会比较happy了,因为发现无论如何A都会被删掉。于是我们就可以把点按度数排个序,然后从小度数的点开始删。

    当然这里还有一个问题需要讨论清,如果A和B的度数相等怎么办?这时删掉A也是无所谓的,因为即便A是完全图中的某个点,那么完全图删掉一个点还会是完全图。那么会不会因为删掉A同时留下B(如果B也能删掉的话肯定就对构成完全图没影响了)而导致不会形成完全图呢?

    这时不妨再讨论一下,如果A和B本来是一个完全图中的两个点的话,自然删A和删B的效果是一样的,不会有影响。如果A和B不是一个完全图中的两个点,那么假设A是完全图中的,这时B必然要被删掉,这样B就会有多余的度数和删掉的集合中的点形成边,反过来假设B是完全图中的点,留B删A也是一样的,因此如果A和B不是一个完全图中的两个点,那么本来就不存在合法的方案,于是删A就当玩玩了,反正是无解的,最后判定一下留下的点会不会形成完全图就行了。总而言之,删A不会产生什么不良的后果。

    讨论到这里,算法基本就成型了:

    基本的思路是将一定会被删掉的点删掉,并保证删掉的点之间没有边,最后看留下的点能否构成完全图。

    先把点按度数升序排序,然后从度数较小的开始删,删掉之后更新与之相连的点的度数,并将那些点标记为“必须留下的点”,当扫描到已标记的点的时候就跳过去。最后看留下的点能不能形成完全图。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXD 50010
#define MAXM 200010
#define INF 0x3f3f3f3f
int N, M, first[MAXD], e, next[MAXM], v[MAXM], dgr[MAXD], isin[MAXD], r[MAXD];
bool cmp(const int &x, const int &y)
{
    return dgr[x] < dgr[y];    
}
void add(int x, int y)
{
    v[e] = y;
    next[e] = first[x], first[x] = e ++;    
}
void init()
{
    int i, x, y;
    memset(first, -1, sizeof(first[0]) * (N + 1)), e = 0;
    memset(dgr, 0, sizeof(dgr[0]) * (N + 1));
    for(i = 0; i < M; i ++)
    {
        scanf("%d%d", &x, &y);
        ++ dgr[x], ++ dgr[y];
        add(x, y), add(y, x);
    }
}
void solve()
{
    int i, j, x, cnt = 0, min = INF;
    memset(isin, 0, sizeof(isin[0]) * (N + 1));
    for(i = 1; i <= N; i ++) r[i] = i;
    std::sort(r + 1, r + 1 + N, cmp);
    for(i = 1; i <= N; i ++)
        if(!isin[x = r[i]])
        {
            for(j = first[x]; j != -1; j = next[j])
                -- dgr[v[j]], isin[v[j]] = 1;
        }
    for(i = 1; i <= N; i ++)
        if(isin[x = r[i]])
            ++ cnt, min = std::min(min, dgr[x]);
    printf("%s\n", cnt == min + 1 ? "Y" : "N");
}
int main()
{
    while(scanf("%d%d", &N, &M), N)
    {
        if(M == 0)
        {
            printf("Y\n");
            continue;    
        }
        init();
        solve();    
    }
    return 0;    
}

解题转自:http://www.cnblogs.com/staginner/archive/2012/08/21/2648919.html


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。