1227图论，
给出一些点和点之间的无向边，问能否找到一条有向路径其长度大于等于指定长度
分析:如果图中有环路，则一定可以（有环路说明可以绕着该环一直走）
或者存在一条长度大于等于指定长度的一条通路。
竟然发现自己不会在图中找环，写了近两个小时都没把这个找环的内容处理好。
还是从网上荡下来一个。
从每个点开始做一遍dfs找到最大若有点回到该点则说明有环路，
要么就dfs出一条最长的通路。
1
#include<cstdio>
2#include<cstring>
3using namespace std;
4#define MN 101
5int map[MN][MN];
6int flag[MN];
7int n,root,cost,f;
8void dfs(int x,int s)
9
{
10
if(f)
11 return ;
12 if(s>=cost)
13
{
14 f=1;
15 return ;
16
}
17 for(int i=1;i<=n;i++)
18 {
19 if(!flag[i]&&map[x][i])
20 {
21 int tmp=map[x][i];
22 map[x][i]=map[i][x]=0; //选择了该条边在最长路上
23 flag[i]=1;
24 if(i==root) //有环路
25 {
26 f=1;
27 return ;
28 }
29 dfs(i,s+tmp);
30 map[x][i]=map[i][x]=tmp; //不选择这条边在最长路上
31 flag[i]=0;
32 if(f)
33 return;
34 }
35 }
36
}
37int main()
38{
39 int m,i,a,b,d;
40 while(scanf("%d%d%d",&n,&m,&cost)!=EOF)
41 {
42 memset(flag,0,sizeof(flag));
43 memset(map,0,sizeof(map));
44 f=0;
45 for(i=0;i<m;i++)
46 {
47 scanf("%d%d%d",&a,&b,&d);
48 if(!map[a][b])
49 map[a][b]=map[b][a]=d;
50 else
51 f=1;
52 }
53 for(i=1;i<=n&&!f;i++)
54 {
55 memset(flag,0,sizeof(flag));
56 root=i;
57 dfs(i,0);
58 }
59 if(f)
60 puts("YES");
61 else
62 puts("NO");
63 }
64 return 0;
65}