7-22 669 views
题意:对于每组数据,判断是否存在负环
思路:SPFA找负环,此题数据非常强大。根据信息学奥赛一本通·提高篇中所述,DFS-SPFA找负环速度很快,实际上并不是这样,直接TLE。
之前用的普通BFS-SPFA模版也一样TLE,在题解区发现有一种新写法,更新时用cnt[v]=c[u]+1取代cnt[v]++,速度快了一倍左右,正确性有待考证,做了几道题目到目前为止没有发现问题。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; const int MAXN=2005; const int INF=0x3f3f3f3f; int n,m; struct Edge { int v; int cost; Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {} }; vector<Edge>E[MAXN]; void addedge(int u,int v,int w) { E[u].push_back(Edge(v,w)); } bool vis[MAXN];//在队列标志 int cnt[MAXN];//每个点的入队列次数 int dist[MAXN]; bool SPFA() { queue<int>que; while(!que.empty())que.pop(); for(int i=1; i<=n; i++) { vis[i]=false; dist[i]=INF; cnt[i]=0; } que.push(1); cnt[1]=1; dist[1]=0; while(!que.empty()) { int u=que.front(); que.pop(); vis[u]=false; for(int i=0; i<E[u].size(); i++) { int v=E[u][i].v; if(dist[v]>dist[u]+E[u][i].cost) { dist[v]=dist[u]+E[u][i].cost; if(!vis[v]) { cnt[v]=cnt[u]+1; //cnt[v]++; if(cnt[v]>n)return true; vis[v]=true; que.push(v); } } } } return false; } int main() { int ww; scanf("%d",&ww); while (ww--) { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) E[i].clear(); for (int i=0; i<m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); if (c>=0) addedge(b,a,c); } bool flag=SPFA(); if (flag) printf("YE5\n"); else printf("N0\n"); } return 0; }
Latest posts by 青鸟千秋 (see all)
- Ceph客户端缓存一致性分析 - 2019年6月21日
- CephFS:什么是CAPS? - 2019年6月21日
- Ceph集群快速搭建教程 - 2019年6月20日