URAL 1227 Rally Championship（树的直径）（无向图判环）

1227. Rally Championship

Time limit: 1.0 second
Memory limit: 64 MB

A
high-level international rally championship is about to be held. The
rules of the race state that the race is held on ordinary roads and the
route has a fixed length. You are given a map of the cities and two-way
roads connecting it. To make the race safer it is held on one-way roads.
The race may start and finish anyplace on the road. Determine if it is
possible to make a route having a given length S.

Input

The first line of the input contains integers M, N and S that are the number of cities, the number of roads the length of the route (1 ≤ M ≤ 100; 1 ≤ N ≤ 10 000; 1 ≤ S ≤ 2 · 10⁶).

The following N lines describe the roads as triples of integers: P, Q, R. Here P and Q are cities connected with a road, and R is the length of this road. All numbers satisfy the following restrictions: 1 ≤ P, Q ≤ M; 1 ≤ R ≤ 32000.

Output

Write
YES to the output if it is possible to make a required route and NO
otherwise. Note that answer must be written in capital Latin letters.

Samples

input	output
3 2 20 1 2 10 2 3 5	NO
3 3 1000 1 2 1 2 3 1 1 3 1	YES

Problem Source: 2002-2003 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk,

【分析】先判断是否有环，如果有则YES，没有的话找最大直径，如果大于等于s，则YES，其他情况则NO。注意有图不连通情况。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <string>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof a)

typedef long long ll;

using namespace std;

const int N = ;

const int M = ;

int n,m,cnt=;

int tot=,s,t,son,sum;

int head[N],dis[N],vis[N],pre[N],vis1[N];

int w[N][N];

int in[N],out[N];

int  bfs(int x) {

    met(vis,);

    met(dis,);

    sum=;

    queue<int>Q;

    Q.push(x);

    vis[x]=;vis1[x]=;

    while(!Q.empty()) {

        int t=Q.front();

        Q.pop();//printf("t=%d\n",t);

        bool has=false;

        for(int i=; i<=n; i++) {

            if(!vis[i]&&w[t][i]!=) {

                Q.push(i);

                dis[i]=dis[t]+w[t][i];

                vis[i]=vis1[i]=;

                has=true;

            }

        }

        if(!has) {

            if(dis[t]>sum) {

                sum=dis[t];

                //printf("%d %d\n",sum,dis[t]);

                son=t;

            }

        }

    }

    return sum;

}

int main() {

    int u,v,l,sum=;

    scanf("%d%d%d",&n,&m,&s);

    while(m--) {

        scanf("%d%d%d",&u,&v,&l);

        w[u][v]=w[v][u]=l;

        in[u]++;

        in[v]++;

    }

    queue<int>q;

    for(int i=; i<=n; i++) {

        if(in[i]<=)q.push(i);

    }

    while(!q.empty()) {

        int t=q.front();

        q.pop();

        vis[t]=;

        for(int i=; i<=n; i++) {

            if(!vis[i]&&w[t][i]!=) {

                in[i]--;

                if(in[i]==)q.push(i);

            }

        }

    }

    bool flag=false;

    for(int i=; i<=n; i++) {

        if(!vis[i])flag=true;

    }

    if(flag)printf("YES\n");

    else {

        int ans=-;

        memset(vis1,,sizeof vis1);

        for(int i=; i<=n; i++)

            if(!vis1[i]) {

                bfs(i);

                ans=max(ans,bfs(son));

            }

        if(ans>=s)puts("YES");

        else puts("NO");

    }

    return ;

}

巴特西

URAL 1227 Rally Championship（树的直径）（无向图判环）

1227. Rally Championship

Input

Output

Samples

最新文章

热门文章