• 题意: 无向图加负的有向边,求是否存在负环
• 思路:
  1. spfa: spfa是一直拿更新后的边来增广其他可达边,如果存在负环,则会一直增广,存下当前路径的长度,如果超过了n则说明一直在负环上增广,即存在负环
  2. floyd: 跑一遍Floyd,如果存在某个点到自己的距离为负,则存在负环(负环上的点走一遍负环,到自己的距离肯定为负)

spfa:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define ll long long#define FOR(i,l,r) for(int i = l ; i <= r ;++i )#define inf 0x3f3f3f3f#define EPS (1e-9)#define ALL(T)  T.begin(),T.end()using namespace std;const int maxn = 5010;int n,m,w;struct Edge{    int to,next,w;}edge[maxn*10];int tot;int d[maxn],cnt[maxn],head[maxn];int v[maxn];void addEdge(int u,int v,int w){    edge[tot].to = v;    edge[tot].w = w;    edge[tot].next = head[u];    head[u] = tot++; }bool spfa(){    queue
         
           q; memset(v,0,sizeof(v)); memset(cnt,0,sizeof(cnt)); d[1] = 0; cnt[1] = 0; v[1] = 1; q.push(1); while(q.size()){ int x = q.front(); q.pop(); v[x] = 0; for(int i=head[x];i!=-1;i=edge[i].next){ int y = edge[i].to; int z = edge[i].w; if(d[y]>d[x]+z){ d[y] = d[x]+z; cnt[y] = cnt[x] + 1; if(cnt[y]>n) return true; if(v[y]==0){ q.push(y); v[y] =1; // cnt[y]++; } } } } return false;}int main(){int t;cin >> t;while(t--){ cin >> n >> m >> w; tot = 0; int f,to,wet; memset(head,-1,sizeof(head)); memset(d,inf,sizeof(d)); for(int i=1;i<=m;++i){ cin >> f >> to >> wet; addEdge(f,to,wet); addEdge(to,f,wet); } for(int i=1;i<=w;++i){ cin >> f >> to >> wet; addEdge(f,to,-wet); } if(spfa())cout << "YES" << endl; else cout <<"NO" << endl;} return 0;}
         
        
       
      
     
    

floyd:

#include
    
     #include
     
      #include
      
       using namespace std;const int maxn = 510;inline int read(){   int s=0,w=1;   char ch=getchar();   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();   return s*w;}int n,m,w;int g[maxn][maxn];inline int min(int a,int b){    return a>b? b:a;}bool floyd(){    for(int k=1;k<=n;++k){        for(int i=1;i<=n;++i){            for(int j=1;j<=n;++j){                if(g[i][j]>g[i][k]+g[k][j])                    g[i][j] =  g[i][k]+g[k][j];            }            if(g[i][i]<0){                return true;            }        }    }    return false;}int main(){int t;t = read();while(t--){    n = read(); m = read(); w = read();    memset(g,0x3f,sizeof(g));    for(int i=1;i<=n;++i)   g[i][i] = 0;    int f,to,wet;    for(int i=1;i<=m;++i){        f = read(); to = read();    wet = read();        g[f][to] = wet
      
     
    

floyd加快读 1.6s用min会T,用三目运算符也会T,用if才能过神奇, spfa加cin 0.5s