URAL 1227 Rally Championship（树的直径）（无向图判环）-白红宇

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

阅读量：6882 次

发布时间：2019-06-27

本文共 2777 字，大约阅读时间需要 9 分钟。

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

Input

The first line of the input contains integers

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 ≤

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 201 2 102 3 5	NO
3 3 10001 2 12 3 11 3 1	YES

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

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

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #define inf 0x3f3f3f3f#define met(a,b) memset(a,b,sizeof a)typedef long long ll;using namespace std;const int N = 10005;const int M = 24005;int n,m,cnt=0;int tot=0,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,0); met(dis,0); sum=0; queue
               
                Q; Q.push(x); vis[x]=1;vis1[x]=1; while(!Q.empty()) { int t=Q.front(); Q.pop();//printf("t=%d\n",t); bool has=false; for(int i=1; i<=n; i++) { if(!vis[i]&&w[t][i]!=0) { Q.push(i); dis[i]=dis[t]+w[t][i]; vis[i]=vis1[i]=1; 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=0; 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
                
                 q; for(int i=1; i<=n; i++) { if(in[i]<=1)q.push(i); } while(!q.empty()) { int t=q.front(); q.pop(); vis[t]=1; for(int i=1; i<=n; i++) { if(!vis[i]&&w[t][i]!=0) { in[i]--; if(in[i]==1)q.push(i); } } } bool flag=false; for(int i=1; i<=n; i++) { if(!vis[i])flag=true; } if(flag)printf("YES\n"); else { int ans=-1; memset(vis1,0,sizeof vis1); for(int i=1; i<=n; i++) if(!vis1[i]) { bfs(i); ans=max(ans,bfs(son)); } if(ans>=s)puts("YES"); else puts("NO"); } return 0;}

转载于:https://www.cnblogs.com/jianrenfang/p/5986261.html

你可能感兴趣的文章