100729 G 解题报告
题目链接:http://codeforces.com/gym/100729/attachments/download/3754/20112012-northwestern-european-regional-contest-nwerc-2011-en.pdf
这道题大概意思:
给你m个条件,n个人的坐标
"A听到,B比C先开枪"
然而,你需要考虑340m/s的声速的问题
所以,现在你要求出真正的开枪顺序,如果不能确定"UNKNOWN"信息有误"IMPOSSIBLE"
我们来考虑
A先听到B而不是C
那么就有B-->C的一条边
代表在C发枪val(b,c)秒后,B一定会发枪
那么我们floyd一次
如果出现val(i,i)<0,代表在i发枪前i秒,i一定会发枪,显然错,Impossible
如果出现val(i,j)>0且val(j,i)>0且i!=j,代表i和j之间发枪关系没定,显然Unknown了
其他情况,直接暴力找val全<0的即可.注意不要在任何时候去统计没发枪的人.
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | #include<set>#include<map>#include<list>#include<queue>#include<stack>#include<math.h>#include<string>#include<time.h>#include<bitset>#include<vector>#include<memory>#include<utility>#include<stdio.h>#include<sstream>#include<fstream>#include<iostream>#include<stdlib.h>#include<string.h>#include<algorithm>using namespace std;map<string,int> ma;int x[105],y[105];char a[1005];double dist[105][105];double val[105][105];bool gun[105];string name[1005];int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int t; scanf("%d",&t); int zu; for (zu=0;zu<t;zu++) { ma.clear(); int n,m; scanf("%d%d",&n,&m); int i; for (i=0;i<n;i++) { scanf("%s%d%d",a,&x[i],&y[i]); string b=a; ma[b]=i; name[i]=b; } for (i=0;i<n;i++) { int j; for (j=0;j<n;j++) { dist[i][j]=sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j])); val[i][j]=1e12; } gun[i]=false; } int j,k; for (i=0;i<m;i++) { scanf("%s",a); string b=a; int x=ma[b]; scanf("%s",a); scanf("%s",a); b=a; int y=ma[b]; scanf("%s",a); scanf("%s",a); scanf("%s",a); b=a; int z=ma[b]; val[y][z]=min(val[y][z],dist[x][z]-dist[x][y]); gun[y]=true; gun[z]=true; } for (k=0;k<n;k++) { for (i=0;i<n;i++) { for (j=0;j<n;j++) { if ((k==i)||(k==j)) continue; val[i][j]=min(val[i][j],val[i][k]+val[k][j]); } } } for (i=0;i<n;i++) { if (val[i][i]<0) { puts("IMPOSSIBLE"); break; } } if (i!=n) continue; for (i=0;i<n;i++) { if (!gun[i]) continue; int j; for (j=0;j<n;j++) { if (!gun[j]) continue; if (i==j) continue; if ((val[i][j]>0)&&(val[j][i]>0)) { puts("UNKNOWN"); break; } } if (j!=n) break; } if (i==n) { for (k=0;k<n;k++) { for (i=0;i<n;i++) { if (!gun[i]) continue; for (j=0;j<n;j++) { if (!gun[j]) continue; if (i==j) continue; if (val[i][j]>0) break; } if (j==n) { printf("%s ",name[i].c_str()); gun[i]=false; break; } } } puts(""); } } return 0;} |
评论 (0)