简单的dfs 但繁琐的可以了 0.0
#include#include #include 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;}