现在的位置: 首页 > 综合 > 正文

HDU 1258 确定比赛名次 &&HDU 3342 Legal or Not 【临接表+拓扑排序】

2018年05月16日 ⁄ 综合 ⁄ 共 3764字 ⁄ 字号 评论关闭

HDU 1258 链接:click here

HDU 3342 链接:click here

题意:

确定比赛名次

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14142    Accepted Submission(s): 5667

Problem Description
有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。
 

Input
输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。
 

Output
给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。

其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。

 

Sample Input
4 3 1 2 2 3 4 3
 

Sample Output
1 2 4 3
 【解题思路】:
 基础的拓扑排序应用:
/* 拓扑排序方法如下:

  (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.

  (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.

  (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
*/

代码:

//HDU 1285 确定比赛名次
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn =550;
int G[maxn][maxn];
int indegree[maxn];
int V,m;
bool g[maxn];
void AOV_topsort( )
{
    int flag = 1;
    for( int i=1 ; i<V+1 ; i++ )
    {
        for( int j=1 ; j<V+1 ; j++ )
        {
            if(indegree[j] == 0 )
            {
                if(i!=V)
                    printf("%d ",j);
                else printf("%d\n",j);
                indegree[j]--;
                for(int k=1 ; k<V+1; k++ )
                {
                    if(G[j][k] == 1 )
                    {
                        indegree[k]--;
                    }
                }
                break;
 
            }
        }
    }
}
int main()
{
    while(cin>>V>>m)
    {
        memset(G ,0 ,sizeof(G) );
        memset(g,false,sizeof(g) );
        memset(indegree ,0,sizeof(indegree) );
        int a,b;
        for( int i=0 ; i<m ; i++ )
        {
            scanf("%d%d",&a,&b);
            if(G[a][b]==0)
            {
                G[a][b]=1;
                indegree[b]++;
            }
        }
        AOV_topsort( );
    }
    return 0;
}
 

Legal or Not

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5041    Accepted Submission(s): 2311

Problem Description
ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When
someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are
too many masters and too many prentices, how can we know whether it is legal or not?

We all know a master can have many prentices and a prentice may have a lot of masters too, it's legal. Nevertheless,some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian's master and, at the same time, 3xian
is HH's master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not.

Please note that the "master and prentice" relation is transitive. It means that if A is B's master ans B is C's master, then A is C's master.

 
Input
The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which
means x is y's master and y is x's prentice. The input is terminated by N = 0.
TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,..., N-1). We use their numbers instead of their names.

Output
For each test case, print in one line the judgement of the messy relationship.
If it is legal, output "YES", otherwise "NO".
 
Sample Input
3 2 0 1 1 2 2 2 0 1 1 0 0 0
 
Sample Output
YES NO

【解题思路】

跟上一题思路一样,注意判重

代码:

/* 拓扑排序方法如下:

  (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.

  (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.

  (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
*/
 //HDU 3342 Legal or Not
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn =550;
int G[maxn][maxn];
int indegree[maxn];
int V,m;
bool g[maxn];
void AOV_topsort( )
{
    int flag = 1;
    for( int i=1 ; i<V+1 ; i++ )
    {
        for( int j=0 ; j<V ; j++ )
        {
            if(indegree[j] == 0 )
            {
                if(g[j]==0)
                {
                    g[j]=1;
                    indegree[j]--;
                    for(int k=0 ; k<V; k++ )
                    {
                        if(G[j][k] == 1 )
                        {
                            indegree[k]--;
                        }
                    }
                }
            }
        }
    }
    for(int i=0 ; i<V ; i++ )
        if(indegree[i]> 0)
        {
            flag = 0;
            break;
        }
    if(flag==0)
        puts("NO");
    else
        puts("YES");
}
int main()
{
    while(cin>>V>>m&&V&&m)
    {
        memset(G ,0 ,sizeof(G) );
        memset(g,false,sizeof(g) );
        memset(indegree ,0,sizeof(indegree) );
        int a,b;
        for(int i=0 ; i<m ; i++ )
        {
            cin>>a>>b;
            if(G[a][b]==0)
            {
                G[a][b]=1;
                indegree[b]++;
            }
        }
        int flag = 0;
        for(int i=0; i<V; i++)
        {
            if(indegree[i]==0)
            {
                flag = 1;
                break;
            }
        }
        if(flag==0) puts("NO");
        else     AOV_topsort( );
    }
    return 0;
}
 

抱歉!评论已关闭.