题目链接
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.
Input
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.
Output
For each team in the same order as the team list in the input, print one line of the following form:
Team XXX can finish as high as nth place and as low as mth place.
Use st, nd, and rd instead of th for first, second, and third place, respectively. Print a blank line
between cases.
Sample Input
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
Sample Output
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.
题意: 球队每场积分只有三种情况，获胜积3分，失败0分，平局积1分。
还有些场 -1:-1是未赛的场次，求每支球队的最好名次和最坏名次
注意名次输出（复制样例）第一（1st）第二(2nd)第三（3rd） 其他（nth）
code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2000;
const int inf = 0x3f3f3f3f;
map<string,int>Hash;
string Team[maxn];
char tmp[60];
int n,m;
int L;
struct node1{
    int t1,t2;
}Tie[60];
struct node
{
    int id,score;
    bool operator <(const node &b)const
    {
        return score>b.score;
    }
}Q[60];
int score[maxn],minR[maxn],maxR[maxn];
void pos(int id)
{
    if(id==1)printf("1st");
    else if(id==2)printf("2nd");
    else if(id==3)printf("3rd");
    else printf("%dth",id);
}
void dfs(int x)
{
    if(x>L)
    {
       // cout<<"y"<<endl;
        for(int i=1;i<=n;i++)
        {
            Q[i].id = i;
            Q[i].score = score[i];
        }
        sort(Q+1,Q+1+n);
        int last = 1;
        for(int i=1;i<=n;i++)
        {
            int id = Q[i].id,Rank;
            if(Q[i].score==Q[last].score)Rank = last;
            else last = Rank = i;
            if(minR[id]==-1||Rank<minR[id])minR[id] = Rank;
            if(maxR[id]==-1||Rank>maxR[id])maxR[id] = Rank;
        }
        return ;
    }
    score[Tie[x].t1]+=3;
    dfs(x+1);
    score[Tie[x].t1]-=3;
    score[Tie[x].t2]+=3;
    dfs(x+1);
    score[Tie[x].t2]-=3;
    score[Tie[x].t1]++;
    score[Tie[x].t2]++;
    dfs(x+1);
    score[Tie[x].t1]--;
    score[Tie[x].t2]--;
}
int main()
{
     int top = 1;
     while(cin>>n>>m)
     {

         if(n==0&&m==0)break;
         if(top)top =0 ;
         else printf("\n");
         L =0 ;
         string name,temp;
         Hash.clear();
         for(int i=1;i<=n;i++)
         {
             cin>>name;
             Hash[name] = i;
             Team[i] = name;
         }
         memset(score,0,sizeof score);
         memset(minR,-1,sizeof (minR));
         memset(maxR,-1,sizeof (maxR));
         for(int i=1;i<=m;i++)
         {
             scanf("%s",tmp);
             string t1(tmp);
             scanf("%s",tmp);
             scanf("%s",tmp);
             tmp[strlen(tmp)-1] = 0;
             string t2(tmp);
             int x,y;
             scanf("%d%d",&x,&y);
             if(x==-1&&y==-1)
             {
                Tie[++L].t1 = Hash[t1];
                 Tie[L].t2 = Hash[t2];
                 continue;
             }
             if(x>y){
                score[Hash[t1]]+=3;
             }
             else if(x<y)
             {
                 score[Hash[t2]]+=3;
             }
             else
             {
                 score[Hash[t1]]+=1;
                 score[Hash[t2]]+=1;
             }
         }
         dfs(1);
         for(int i=1;i<=n;i++)
         {
             printf("Team %s can finish as high as ",Team[i].c_str());
             pos(minR[i]);
             printf(" place and as low as ");
             pos(maxR[i]);
             printf(" place.\n");
         }
      // puts("");
     }
  return 0 ;
}