首页 > 搜索 > DFS搜索 > HDU 3778-Soccer-DFS-[解题报告]HOJ
2015
04-10

HDU 3778-Soccer-DFS-[解题报告]HOJ

Soccer

问题描述 :

In soccer, there are many different rewards (and punishments) depending on how you rank in the league at the end of a season. For example, in the British Premier League, the top 4 teams are eligible to play in the Champions League, the next team is eligible to play in the Europa League, and the bottom three teams are relegated to the lower division. It is now near the end of the soccer season, and there are still a number of games to be played. For any given team, we wish to know what is the highest and lowest rank it can have at the end of the season.

For each game played, a team wins if it scores more goals than its opponent. A team loses a game if it scores fewer goals. When both teams score the same number of goals, we call it a draw. A team earns 3 points for each win, 1 point for each draw and 0 point for each loss. Teams are ranked according to the number of points earned (more points result in a higher ranking). Teams that are tied are given the same rank. For example, if two teams are tied and have the next highest point total after the 3rd place team, then they are both ranked 4th (and the next team is ranked 6th). In real life, factors such as goal differences and goals scored are used to break ties, but we will not consider these for this problem.

You are given a list of soccer teams and a list of matches in a season. You may assume that every team will play the same number of games at the end. Some of the matches have been played and the results are known.

输入:

The input consists of a number of cases. The first line in each case specifies two integers n and m (2≤n≤20, 1≤m≤1000) indicating the number of teams in the league and the number of matches in the season. The next n lines contain the name of each team in its own line. The team names contain only alphabetic characters and have lengths at most 30 characters. This is followed by m lines each of the form

team1 vs team2: x y

with team1 and team2 being the names of two different teams, and x and y are non-negative integers (or both are -1), indicating that in the game between team1 and team2, team1 scores x goals and team2 scores y goals. If both x and y are -1, then the game has not yet been played. At most 12 games will not have been played yet.

The input is terminated with n = m = 0.

输出:

The input consists of a number of cases. The first line in each case specifies two integers n and m (2≤n≤20, 1≤m≤1000) indicating the number of teams in the league and the number of matches in the season. The next n lines contain the name of each team in its own line. The team names contain only alphabetic characters and have lengths at most 30 characters. This is followed by m lines each of the form

team1 vs team2: x y

with team1 and team2 being the names of two different teams, and x and y are non-negative integers (or both are -1), indicating that in the game between team1 and team2, team1 scores x goals and team2 scores y goals. If both x and y are -1, then the game has not yet been played. At most 12 games will not have been played yet.

The input is terminated with n = m = 0.

样例输入:

4 6
ManUnited
Arsenal
Chelsea
Tottenham
ManUnited vs Arsenal: 3 1
Chelsea vs Arsenal: 2 2
ManUnited vs Chelsea: 1 0
Tottenham vs ManUnited: -1 -1
Tottenham vs Chelsea: 0 4
Tottenham vs Arsenal: -1 -1
0 0

样例输出:

Team ManUnited can finish as high as 1st place and as low as 1st place.
Team Arsenal can finish as high as 2nd place and as low as 4th place.
Team Chelsea can finish as high as 2nd place and as low as 3rd place.
Team Tottenham can finish as high as 1st place and as low as 4th place.

简单的dfs  但繁琐的可以了 0.0

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
int n,m,cnt=0;
struct team
{
    char s[50];
    int low,up,d,f;
};
team a[30];
struct match
{
    int x,y,re;
    bool operator < (const match &p) const
    {
        return re < p.re;
    }
};
match b[2000];
int find(char *s)
{
    for(int i = 0; i < n; i++)
        if(strcmp(a[i].s, s) == 0)
            return i;
    return -1;
}

void cc(int w)
{
    for(int i = 0; i < n; i++)
        a[i].f = a[i].d;
    for(int i = 0; i < w; i++)
        if(b[i].re == 1)
        {
            a[b[i].x].f += 1;
            a[b[i].y].f += 1;
        }
        else if(b[i].re == 2)
            a[b[i].x].f += 3;
        else
            a[b[i].y].f += 3;
    for(int i = 0; i < n; i++)
    {
        int rank=1;
        for(int j = 0; j < n; j++)
        {
            if(j != i && a[j].f > a[i].f)
                rank++;
        }
        if(rank > a[i].low)
            a[i].low = rank;
        if(rank < a[i].up)
            a[i].up = rank;
    }
}
void dfs(int cur,int w)
{
    if(cur == w)
        cc(w);
    else
    {
        for(int i = 1; i <= 3; i++)
        {
            b[cur].re = i;
            dfs(cur+1, w);
        }
        b[cur].re = 0;
    }
}
void show(int a)
{
    if(a == 1)
        printf("1st ");
    else if(a == 2)
        printf("2nd ");
    else if(a == 3)
        printf("3rd ");
    else
        printf("%dth ", a);
}

void show(team a)
{
    printf("Team %s can finish as high as ",a.s);
    show(a.up);
    printf("place and as low as ");
    show(a.low);
    printf("place.\n");
}
int main()
{
    while(scanf("%d%d",&n,&m) && m+n)
    {
        if(cnt++)
            printf("\n");
        int p,q;
        char u[100],v[100];
        for(int i = 0; i < n; i++)
        {
            scanf("%s",a[i].s);
            a[i].d = a[i].low = 0, a[i].up = 50;
        }
        for(int i = 0; i < m; i++)
        {
            scanf("%s vs %s%d%d",u,v,&p,&q);
            v[strlen(v)-1] = '\0';
            b[i].x = find(u);
            b[i].y = find(v);
            int &re = b[i].re;
            if(p==-1 && q==-1)
                re = 0;
            else if(p == q)
                re = 1;
            else if(p > q)
                re = 2;
            else
                re = 3;
        }
        sort(b, b+m);
        int j = 0;
        for(j = 0; j < m; j++)
            if(b[j].re != 0)
                break;
        for(int i = j; i < m; i++)
            if(b[i].re == 1)
            {
                a[b[i].x].d += 1;
                a[b[i].y].d += 1;
            }
            else if(b[i].re == 2)
                a[b[i].x].d += 3;
            else
                a[b[i].y].d += 3;
        dfs(0, j);
        for(int i = 0; i < n; i++)
            show(a[i]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xlc2845321/article/details/9935503


,
  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.