题目链接: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的即可.注意不要在任何时候去统计没发枪的人.

代码:

#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;
}