ural 1227 dfs判环&求最长路

问题可以简化为求最长路，因为边权均为正，所以有环即意味着最长路是正无穷必定有解；而无环的情况可以以每个点为起点进行dfs求出以该点为起点的最长路如果不小于s即有解。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int INF = 999999999;
 7 const int N = 101;
 8 const int M = 20000;
 9 bool visit[N];
10 int g[N][N];
11 int n, m, s;
12 
13 int dfs( int u, int fa )
14 {
15     int res = 0;
16     visit[u] = 1;
17     for ( int i = 1; i <= n; i++ )
18     {
19         if ( !g[u][i] ) continue;
20         if ( i == fa ) continue;
21         if ( visit[i] )
22         {
23             visit[u] = 0;
24             return INF;
25         }
26         int tmp = dfs( i, u );
27         if ( tmp == INF )
28         {
29             visit[u] = 0;
30             return INF;
31         }
32         res = max( res, g[u][i] + tmp );
33     }
34     visit[u] = 0;
35     return res;
36 }
37 
38 int main ()
39 {
40     while ( scanf("%d%d%d", &n, &m, &s) != EOF )
41     {
42         memset( g, 0, sizeof(g) );
43         bool flag = false;
44         while ( m-- )
45         {
46             int u, v, w;
47             scanf("%d%d%d", &u, &v, &w);
48             if ( g[u][v] || u == v )
49             {
50                 flag = true;
51             }
52             g[u][v] = g[v][u] = w;
53         }
54         if ( flag )
55         {
56             puts("YES");
57             continue;
58         }
59         memset( visit, 0, sizeof(visit) );
60         for ( int i = 1; i <= n; i++ )
61         {
62             if ( dfs( i, -1 ) >= s )
63             {
64                 flag = true;
65                 break;
66             }
67         }
68         puts( flag ? "YES" : "NO" );
69     }
70     return 0;
71 }