首页 > ACM题库 > HDU-杭电 > HDU 3005-The Different World-连通性问题-[解题报告]HOJ
2014
02-27

HDU 3005-The Different World-连通性问题-[解题报告]HOJ

The Different World

问题描述 :

The conflict between two-dimensional world TWO and three-dimensional world THREE had lasted for thousands years.Until the THREE won the TWO on the world war,this conflict was finished by the result—-the TWO became the colonial country of THREE.
People of TWO became the slaves of THREE.The king of THREE decided to establish a monument to remember this historic event.
The monument is one cube for King’s preference.The small cube which has one unit length is the material to build this monument,and the slaves had to finish this project.
The King had many strict requirements.
(1)The workers can not move the materials until the materials can form a flat square.
(2)Only m workers to move the material.
(3)In the process of moving,the first worker only can move the square which has length k+1,the second can move k+2′s square,and so on,the mth worker move the lenth k+m’s square.
When all the materials have reached the target,the workers find that the king is an outstanding mathematician.Because the materials can just build one monument has length m.For example m=47,k=21,can build the monument with length m.
Follow all the requriments,with different m and k, how many cube can be the king’s monument?Could you sort all the monument with length by ascending sort.Then,when the king wants the Nth monument,could you give out the m and k of the Nth monument.The last problem is the important.

输入:

The input contains many test cases.Each test case contains only one line of one integer, N(N<=100).When N=0,the input file is end.

输出:

The input contains many test cases.Each test case contains only one line of one integer, N(N<=100).When N=0,the input file is end.

样例输入:

1
2
0

样例输出:

47 21
2161 988  

/*

 

题目:

    现给出各位选手的能力比较并给出自己的朋友的参赛号码,如何组织比赛使得自己的朋友能够获胜

 

分析:

    各选手能力比较可以构造一个有向图,而想要使得自己的朋友要赢得比赛,所以他的所在的连通块

    必定是入度为0的(假设建图时是以能力大的人作为边的起点)。所以题目可以转换为先建图,然后

    再找连通块求缩点,然后判断该缩点是否入度为0,若有朋友在该连通块中,即可判断可以组织这样

    的一场比赛。而判断朋友在不在该连通块中,可以先求到所有的入度为0的连通块用数组置为true,

    然后直接把所有朋友的所在的连通块置为false,若所有的连通块中只要还有true的连通块,就可判断

    不能组织这样的一场比赛

 

*/

#include <cstdio>

#include <cstring>

 

const int X = 100005;

 

int dfn[X],low[X],stack[X],deg[X],father[X],depth,top,bcnt;

int f[X],fri,n,m;

bool use[X],instack[X];

 

struct node

{

    int v;

    node *next;

    void fun()

    {

        v = 0;

        next = NULL;

    }

}edge[X],*head[X],*tmp;

 

void tarjan(int u)

{

    int v;

    dfn[u] = low[u] = ++depth;

    stack[++top] = u;

    instack[u] = true;

 

    for(node *p=head[u];p;p=p->next)

    {

        v = p->v;

        if(!low[v])

        {

            tarjan(v);

            if(low[v]<low[u])

                low[u] = low[v];

        }

        else if(instack[v]&&low[u]>dfn[v])

            low[u] = dfn[v];

    }

    if(low[u]==dfn[u])

    {

        bcnt++;

        do

        {

            v = stack[top--];

            instack[v] = false;

            father[v] = bcnt;

        }while(u!=v);

    }

}

 

void solve()

{

    memset(instack,false,sizeof(instack));

    memset(low,0,sizeof(low));

    memset(deg,0,sizeof(deg));

    depth = bcnt = top = 0;

 

    for(int i=1;i<=n;i++)

        if(!low[i])

            tarjan(i);

 

    for(int i=1;i<=n;i++)

        for(node *p=head[i];p;p=p->next)

            if(father[i]!=father[p->v])

                deg[father[p->v]]++;

 

    memset(use,false,sizeof(use));

    for(int i=1;i<=bcnt;i++)

        if(!deg[i])

            use[i] = true;

 

    for(int i=0;i<fri;i++)

        use[father[f[i]]] = false;

 

    bool flag = true;

    for(int i=1;i<=bcnt;i++)

        if(use[i])

        {

            flag = false;

            break;

        }

    flag?printf(“yes\n”):printf(“no\n”);

}

 

int main()

{

    freopen(“sum.in”,”r”,stdin);

    freopen(“sum.out”,”w”,stdout);

    while(scanf(“%d%d%d”,&n,&fri,&m),n||m||fri)

    {

        for(int i=0;i<fri;i++)

            scanf(“%d”,&f[i]);

        memset(head,NULL,sizeof(head));

 

        for(int i=0;i<m;i++)

            edge[i].fun();

        tmp = edge;

        int u,v;

        for(int i=0;i<m;i++)

        {

            scanf(“%d%d”,&u,&v);

            tmp->next = head[u];

            tmp->v = v;

            head[u] = tmp++;

        }

        solve();

    }

 

    return 0;

}

参考:http://www.cnblogs.com/yejinru/archive/2012/05/18/2507973.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环