NYOJ 973 天下第一(最长路判环)

NYOJ 973 天下第一(最长路判环)

题目链接：.php?pid=973

题目大意：给你n种武功，每两种武功都可以相互转化，但是有转化率f， 每次必须从一开始转化， 中间有武功转化不了， 后面的就不能在转化了， 问你能否可以无限增加转化。

在做这道题以前做了和这道题一样的一道题， 所以我认为很快就能AC了， 但是这道题我还是弄了一天还是没能AC。来讲一下让我很是郁闷的问题吧。 这道题可以用最短路判环（spfa只需稍微变一下）来做，也可以用直接深搜来做。我的最初想法就是深搜来做。我上一道题就是用深搜做的，我就开始写了， 然后就是各种WA， 后来搞到后台数据找到一组错误的输出， 然后就是各种改， 最终还是WA， 没办法了， 我就写了一个spfa, 然后就AC了， 看来正解还是spfa, 现在我还是不明白我以前的为什么错。所以发个博客记录一下， 以免在出现这种情况。同时想让路过的大牛给解释一下。

下面是代码

AC的

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 500 + 10;
struct Edge
{int v;double f;Edge(int i, double j) : v(i), f(j) {}
};
vector<Edge> G[maxn];
double d[maxn];
int cnt[maxn];
bool inq[maxn];
bool spfa(int s, int n)
{queue<int> Q;memset(inq, false, sizeof(inq));memset(d, 0, sizeof(d));memset(cnt, 0, sizeof(cnt));d[s] = 1.0;inq[s] = true;Q.push(s);while(!Q.empty()){int u = Q.front();Q.pop();inq[u] = false;for(int i = 0; i < G[u].size(); i++){int v = G[u][i].v;double ff = G[u][i].f;if(d[v]<d[u]*ff){d[v] = d[u]*ff;if(!inq[v]){Q.push(v);inq[v] = true;if(++cnt[v] >= n)return true;}}}}return false;
}
int main()
{int T, n, m, a, b;double ff;
//    freopen(&#", "r", stdin);
//    freopen(&#", "w", stdout);scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);for(int i = 0; i <= n; i++)G[i].clear();while(m--){scanf("%d%lf%d", &a, &ff, &b);G[a].push_back(Edge(b, ff));}if(spfa(1, n))puts("Yes");elseputs("No");}return 0;
}

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 500 + 10;
int vis[maxn];
int pre[maxn];
struct Info
{int to;double f;Info(int i, double j) :to(i), f(j) {}
};
vector<Info> G[maxn];
bool dfs(int rt, int u, double ans)
{vis[u] = -1;for(int i = 0; i < G[u].size(); i++){Info x = G[u][i];int v = x.to;pre[v] = pre[u];double Ans = ans * x.f;if(Ans == 0)continue;if(v==rt){if(Ans>1.0)return true;}if(!vis[v] && dfs(rt, v, Ans))return true;}vis[u] = 1;return false;
}
int main()
{int T, n, m;
//    freopen(&#", "r", stdin);
//    freopen(&#", "w", stdout);scanf("%d", &T);while(T--){memset(pre, -1, sizeof(pre));scanf("%d%d", &n, &m);for(int i = 0; i <= n; i++)G[i].clear();while(m--){int a, b;double ff;scanf("%d%lf%d", &a, &ff, &b);G[a].push_back(Info(b, ff));}bool flag = false;pre[1] = 1;for(int i = 1; i <= n; i++){memset(vis, 0, sizeof(vis));if(pre[i]==1 && dfs(i, i, 1.0)){flag = true;break;}}if(flag)printf("Yesn");elseprintf("Non");}return 0;
}

这是深搜的wa的代码，唯一一组出现错误测试数据
33肿武功， 93种转化   应该输出Yes    如果直接暴搜就会超时
33 93
30 0.3 32
23 0.9 6
18 0.9 21
13 0.9 14
21 1.2 11
28 0 24
32 0.5 29
23 1.1 12
26 0.5 8
7 0.1 12
6 1.4 33
29 0.9 30
12 1.3 6
10 0.4 32
33 0.2 6
9 0.5 12
24 1.7 22
4 1 11
3 0.5 1
1 0.8 2
20 0 7
5 1.7 15
13 1.1 16
7 0.7 21
30 0.6 31
18 0.9 10
28 1.7 14
31 0.8 33
27 1.6 15
29 0.4 19
26 0.9 2
23 0.8 5
20 0.4 6
29 1 7
11 1.6 31
30 0.6 17
18 1.5 23
21 1.2 32
21 0.4 16
6 0.3 20
13 0 33
7 0.3 32
14 0.2 4
7 0.3 28
14 0.7 9
17 0.9 28
1 0.1 19
3 0.9 7
11 0.8 29
33 1.9 10
9 0.7 13
7 0.3 17
5 0.1 21
18 0 16
9 1.7 5
11 0.7 10
20 1.2 14
13 0.5 22
29 0.3 23
12 0 21
1 0.1 16
29 1.3 25
1 0.7 29
6 0.9 25
4 0.3 8
27 1.5 14
11 0.5 17
4 1.8 33
32 1.4 26
11 0.2 32
30 0.2 7
29 1.6 5
18 0.2 6
8 0.4 28
23 1.8 33
17 1.3 23
16 0.5 13
22 0.3 26
25 0.7 22
2 1.6 32
16 1.6 26
33 1.8 8
19 0.2 29
28 0.5 13
23 1.8 24
8 0.7 5
19 1.1 23
27 0.9 5
16 0.7 22
19 1.3 9
28 1.9 26
31 0.8 6
25 1 16