首页 > 代码库 > NYIST 973 天下第一
NYIST 973 天下第一
天下第一
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
AC_Grazy一直对江湖羡慕不已,向往着大碗吃肉大碗喝酒的豪情，但是“人在江湖漂,怎能
不挨刀",”人在江湖身不由己",如果自己的武功太差,在江湖会死的很惨，但是AC_Grazy没有
武功秘籍练不了绝世武功.有道是“山重水复疑无路,柳暗花明又一村”,在AC_Grazy家里面
竟然藏着一本书,书名竟然叫做【超级外挂】,竟然能在各种武功之间进行转化,据说是他爷
爷的爷爷的...爷爷传下来的...
闲着无事便拿来看看,只看一眼便再也停不下了,只见上面写着“纵横武林打遍天下无敌手武功心法秘籍收录”.
翻开第一篇一看竟然是【降龙十八掌】...
心法只是一个修练武功的途径,重要的是真气的多少,于是他便想利用外挂让武功之间进行转
化，来让真气无限增加，但是这个心法只能按照顺序转化，我们分别用 1号和2号来代替两种功法 当然转化会有一定的转化率f
比如1 0.5 2 便是把 1的一半真气转化给2 ,为了简化问题，我们每次都从1号秘籍开始进行转化,如果其中一个秘籍转化断了，那么以后的功法就不能转换。
输入
输入：首先输入一个数 T(T<=20)表示T组数据
然后输入两个数n(2<=n<=500)和m(1=<m<=2000)分别表
示有n种秘籍，随后的m行分别输入
秘籍u(n>=u>0) 转化率 f (0<f<=10)秘籍 v.(0<v<=n)
输出
输出：如果可以无限增加真气输出Yes否则输出No.
样例输入
2
3 3
1 2 2
2 2 3
3 2 1
4 3
1 2 2
3 2 4
4 2 3
样例输出
Yes
No
上传者
ACM_王亚龙
解题：最长路，判正圈。。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 510;18 struct arc{19 int to,next;20 double f;21 arc(int x = 0,double y = 0,int z = -1){22 to = x;23 f = y;24 next = z;25 }26 };27 arc e[200000];28 int head[maxn],cnt[maxn],tot,n,m;29 bool in[maxn];30 double d[maxn];31 void add(int u,int v,double f){32 e[tot] = arc(v,f,head[u]);33 head[u] = tot++;34 }35 bool spfa(){36 memset(d,0,sizeof(d));37 queue<int>q;38 memset(cnt,0,sizeof(cnt));39 memset(in,false,sizeof(in));40 q.push(1);41 d[1] = 1;42 while(!q.empty()){43 int u = q.front();44 q.pop();45 in[u] = false;46 for(int i = head[u]; ~i; i = e[i].next){47 if(d[e[i].to] < d[u]*e[i].f){48 d[e[i].to] = d[u]*e[i].f;49 if(!in[e[i].to]){50 in[e[i].to] = true;51 if(++cnt[e[i].to] > n) return true;52 q.push(e[i].to);53 }54 }55 }56 }57 return false;58 }59 int main() {60 int T,u,v;61 double f;62 scanf("%d",&T);63 while(T--){64 scanf("%d %d",&n,&m);65 memset(head,-1,sizeof(head));66 for(int i = tot = 0; i < m; ++i){67 scanf("%d %lf %d",&u,&f,&v);68 add(u,v,f);69 }70 printf("%s\n",spfa()?"Yes":"No");71 }72 return 0;73 }
NYIST 973 天下第一
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。