bf bf film bf rajwap.biz tamil pussy fingering desi pron video coxhamster.mobi sexy girl video open xvideoimage pornfactory.info bihari sexy video download سكس كلاسيك مترجم pornclassic.info سكس عراقي hindixxvidio porno-zona.com dise murga indian old women nude rajwap.biz srxyvidio www sexy videoes com indiansexmms.me sxsi bf مصريات شراميط pornvuku.net نيك احلي كس malligi hotel donfreeporn.mobi bengalixxxvideo tsmil sex youjizz.sex perfect girl xxx hd any porn porntubemovs.info xxx thumbzilla نيك طيز مترجم 3gpjizz.info سكس فى السجن xossip bengali kamporn.mobi indian sex play forced indian sex video indiansexgate.mobi sleeping girl xnxx classic video com 2beeg.me indiangirlssexvideos

传送门

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

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

阅读全文

欢迎留言