2013年8月12日 星期一

2013/8/12 zj d946: D. 阿克圖洛斯‧蒙斯克的煩惱

// http://zerojudge.tw/ShowProblem?problemid=d946
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[100000]; int n, m;
struct edge
{
    int a, b; double s;
}e[100000];
double op[100000], po[100000]; int pi; bool use[100000]; queue<int> que;
bool cmp(double a, double b)
{
    return a < b;
}
int test(double t)
{
   
    for(int i = 0; i < n; i++) v[i].clear();
    for(int i = 0; i < m; i++)
        if( e[i].s > t )
        {
            v[ e[i].a ].push_back( e[i].b );
            v[ e[i].b ].push_back( e[i].a );
        }
    for(int i = 0; i < n; i++) use[i] = 0;
   
    while( !que.empty() ) que.pop();
    use[0] = 1;
    que.push(0);
    while( !que.empty() )
    {
        int f = que.front(); que.pop();
        for(int i = 0; i < v[f].size(); i++)
        {
            if( use[ v[f][i] ] == 0 ){ que.push( v[f][i] ); use[ v[f][i] ] = 1; }
        }  
    }
    for(int i = 0; i < n; i++)
        if( use[i] == 0 ){ return 0 ; }
   
    return 1;
}
int main()
{
    int t; scanf("%d", &t);
   
    while( t-- )
    {
       
        scanf("%d %d", &n, &m);
       
        for(int i = 0; i < m; i++)
        {
            scanf("%d %d %lf", &e[i].a, &e[i].b, &e[i].s);
            op[i] = e[i].s;
        }
       
        sort( op, op+m, cmp);
        po[0] = op[0]; pi = 1;
        for(int i = 1; i < m; i++)
        {
            if( op[i] != op[i-1] ) po[pi++] = op[i];
        }
        if( test(0.00) == 0 ) printf("The empire of Arcturus is ending.\n");
        else if( test( po[0]) == 0 ) printf("%.4lf\n", po[0]);
        else if( test( po[pi-1] ) == 1 ) printf("No way.\n");
        else
        {
            int l = 0; int r = pi - 1;
            while( l != r - 1 )
            {
                int mid = (l+r)/2;
                if( test( po[mid] ) == 1 ) l = mid;
                else r = mid;  
            }
            printf("%.4lf\n", po[r]);
        }
    }
}

沒有留言:

張貼留言