传送门

题意:对于每组数据,判断是否存在负环

思路: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)

CF-1025D Recovering BST(区间dp)

传送门 题意:给定n个整数,问是否能生成一棵BST(二分查找树,左子树都比它小,右子树都比它大),并且有边相连的点权的gcd>1。 思路:区间dp,dp[l][...

阅读全文

牛客网暑期多校第五场E room(费用流)

传送门 题意:有n个宿舍,每个宿舍住4个人,给定去年n个宿舍的人员构成,今年n个4人组合的情况,求最少几个人需要搬寝室。 思路:转化为最小费用最大流解...

阅读全文

HDU-4091 Zombie’s Treasure Chest(暴力)

传送门 题意:有一个容量为n的箱子,和无限多的两种珠宝,体积和价值分别是s1,v1,s2,v2,求能装下的最大价值。 思路:直接暴力枚举会TLE,先计算s1 s2的LC...

阅读全文

欢迎留言