天下第一
时间限制：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
判断环路，用了spfa,判断入队的次数是不是大于等于n。要先把dis[s]设为1.0；
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<queue> #include<math.h> #include<stdlib.h> #define inf 0x3f3f3f3 using namespace std; struct node { int u,v; double w; struct node*next; }*h[2005]; bool vis[2005]; double dis[2005]; int d[2005]; int n,m; void LA(int u,double w,int v) { struct node*p=(struct node*)malloc(sizeof(struct node)); p->v=v; p->w=w; p->next=h[u]; h[u]=p; } void in() { for(int i=0; i<2005; i++) { dis[i]=0; d[i]=0; } } int spfa(int s) { queue<int>q; memset(vis,false,sizeof(vis)); dis[s]=1.0;//自己给自己是1. q.push(s); d[s]++; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; struct node*p; for(p=h[u]; p!=NULL; p=p->next) { int Q=p->v; if(dis[Q]<dis[u]*p->w) { dis[Q]=dis[u]*p->w;//把dis更新为大的。 if(!vis[Q]) { d[Q]++; vis[Q]=true; q.push(Q); if(d[Q]>=n) return 0; } } } } return 1; } int main() { int t; cin>>t; while(t--) { memset(h,0,sizeof(h)); cin>>n>>m; for(int i=0; i<m; i++) { int x,y; double z; cin>>x>>z>>y; LA(x,z,y); } in(); if(spfa(1)==0) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }