题目链接
注意：如果可以无限增加真气输出Yes否则输出No
我直接忽略了这一点，以为只要能一直流传就可以了，只要这个图是个强连通图就行了，以为转化率是没用的数据。。。第一次是提交也不提示WC，一直提示的Runtime我也找不到哪里错了。。。
最后看了下同学的才发现我理解错题意了，学到了新知识，用spfa判环，之前只用过判断负权环
判断路环：如果某点的进队次数>该点的入度，则成环
安利一下扩展知识：点我
#include<stdio.h> #include<string.h> #include<vector> #include<queue> using namespace std; #define max(a,b) a>b?a:b vector<int>e[505]; int in[505]; int in_Q[505]; int vis[505]; double dis[505]; double f[505][505]; int n; bool spfa(int s) { int i,v,u; queue<int>Q; Q.push(s); dis[s]=1; vis[s]=1; in_Q[s]++; while(!Q.empty()) { u=Q.front(); Q.pop(); vis[u]=0; for(i=0;i<e[u].size();i++) { v=e[u][i]; if(dis[v] < dis[u] * f[u][v]) { dis[v]=dis[u]*f[u][v]; if(!vis[v]) { vis[v]=1; Q.push(v); in_Q[v]++; if(in_Q[v] > in[v]) return true; } } } } return false; } void init() { memset(in_Q,0,sizeof(in_Q)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); } int main() { int T; scanf("%d",&T); while(T--) { int m,i,u,v; double c; scanf("%d%d",&n,&m); for(i=0;i<=n;i++) e[i].clear(); memset(f,0,sizeof(f)); memset(in,0,sizeof(in)); for(i=0;i<m;i++) { scanf("%d%lf%d",&u,&c,&v); e[u].push_back(v); f[u][v]=max(f[u][v],c); in[v]++; } init(); if(spfa(1)) printf("Yes\n"); else printf("No\n"); } return 0; } 错误理解的代码也贴上吧~（判断该图否是强连通）
#include<stdio.h> #include<string.h> #include<vector> #include<stack> using namespace std; #define min(a,b) a<b?a:b int Belong[505]; int Bcnt,time; int dfn[505],low[505]; int in_s[505]; int size_s[505]; int n,m; vector<int>e[505]; stack<int>S; void init() { memset(Belong,0,sizeof(Belong)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(in_s,0,sizeof(in_s)); memset(size_s,0,sizeof(size_s)); Bcnt=0; time=0; } void tarjan(int u) { int i,v; S.push(u); in_s[u]=1; dfn[u]=low[u]=++time; for(i=0;i<e[u].size();i++) { v=e[u][i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(in_s[v]) { low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { Bcnt++; do{ v=S.top(); S.pop(); in_s[v]=0; Belong[v]=Bcnt; size_s[Bcnt]++; }while(v!=u); } } } int main() { int T; scanf("%d",&T); while(T--) { int i,u,v; double f; scanf("%d%d",&n,&m); for(i=0;i<=n;i++) e[i].clear(); for(i=0;i<m;i++) { scanf("%d%lf%d",&u,&f,&v); e[u].push_back(v); } init(); for(i=1;i<=n;i++) { if(!dfn[i]) tarjan(i); } if(Bcnt==1 && size_s[1]==n) { printf("Yes\n"); } else printf("No\n"); } return 0; } 明天比赛，给自己加油~
