一个例子教你如何与出题人斗智斗勇

2018-06-17 21:36:21来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

我以前出过一道题,卡了10种贪心,但还是被第11种贪心A了, 

一道题不会做?贪嘛,能怎么贪怎么贪,想怎么贪怎么贪!

现在NOIP题目的数据给的不都很明确嘛,简单,对着数据,一个一个的贪!

 

                         —By 贪心之神CCL

 

 

 

      

 

 

今天做了一道很bt的题

P3385 【模板】负环

这题居然卡广搜SPFA,哎作为一个只会写广搜SPFA的我就不服了 :triumph:

卡我者,必被我贪!:confused:

 

Try First

判断负环嘛,有一个很显然的结论,当你从开始点出发浪了一圈之后又回到开始点,发现还能继续更新,那就一定有负环!

本来以为它给的数据有那种多个联通分量的情况,但事实证明我想多了。:sweat_smile:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int f=1,x=0;
    while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
    while(c>='0'&&c<='9')	x=x*10+c-48,c=getchar();return x*f;
}
struct node
{
    int u,v,w,nxt;
}edge[MAXN];
int head[MAXN];
int num=1;
inline void add_edge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].w=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int inger[MAXN];
int vis[MAXN];
int dis[MAXN];
inline void pre()
{
    memset(head,-1,sizeof(head));
    num=1;
    memset(vis,0,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
}
int n,m;
inline void SPFA()
{
    queue<int>q;
    q.push(1);
    vis[1]=1;dis[1]=0;
    while(q.size()!=0)
    {
        int p=q.front();
        q.pop();
        vis[p]=0;
        for(int i=head[p];i!=-1;i=edge[i].nxt)
        {
            if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
            {
                dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
                if(vis[edge[i].v]==0)
                {
                    vis[edge[i].v]=1;
                    if(edge[i].v==1)
                    {
                        printf("YE5\n");
                        return ;
                    }
                    q.push(edge[i].v);
                }
            }
        }
    }
    printf("N0\n");
}
int main()
{
    int T=read();
    while(T--)
    {
        pre();
        n=read();m=read();
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read(),z=read();
            if(z<0)	add_edge(x,y,z);
            else add_edge(x,y,z),add_edge(y,x,z);
        }
        SPFA();
    }
    return 0;
}

  

 

这样就可以A啦

不过这个貌似有点借鉴dfs的思想了,

它卡的是入队次数,

正常情况下只有一个点入队次数超过n的时候才有负环,但这个太慢了,

我们考虑缩小一下这个n

 

Try Second

n太大了,那怎么办呢?

我们直接随机一个就好啦:grin:

然而。。:dizzy_face: :dizzy_face: :dizzy_face: :dizzy_face: :dizzy_face:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<ctime>
#include<cstdlib>
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int f=1,x=0;
    while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
    while(c>='0'&&c<='9')	x=x*10+c-48,c=getchar();return x*f;
}
struct node
{
    int u,v,w,nxt;
}edge[MAXN];
int head[MAXN];
int num=1;
inline void add_edge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].w=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int inger[MAXN];
int vis[MAXN];
int dis[MAXN];
inline void pre()
{
    memset(head,-1,sizeof(head));
    num=1;
    memset(inger,0,sizeof(inger));
    memset(vis,0,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
}
int n,m,Attack;
inline void SPFA()
{
    queue<int>q;
    q.push(1);
    vis[1]=1;dis[1]=0;
    while(q.size()!=0)
    {
        int p=q.front();
        q.pop();
        vis[p]=0;
        for(int i=head[p];i!=-1;i=edge[i].nxt)
        {
            if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
            {
                dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
                if(vis[edge[i].v]==0)
                {
                    vis[edge[i].v]=1;
                    inger[edge[i].v]++;
                    if(inger[edge[i].v]>=Attack)
                    {
                        printf("YE5\n");
                        return ;
                    }
                    q.push(edge[i].v);
                }
            }
        }
    }
    printf("N0\n");
}
int main()
{
    srand((unsigned)time(NULL));
    
    int T=read();
    while(T--)
    {
        pre();
        n=read();m=read();
        Attack=rand()%n^rand()%n&rand()%n;
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read(),z=read();
            if(z<0)	add_edge(x,y,z);
            else add_edge(x,y,z),add_edge(y,x,z);
        }
        SPFA();
    }
    return 0;
}

  

 

Try Third

 

看来rand是不行了

我们来指定一下吧

像这样:

if(inger[edge[i].v]>=250)
{
    printf("YE5\n");
    return ;
}

250

 

 200

 

100

 

。。。。:angry:

 

 

 

 

20

:grinning:  :grinning:  :grinning:   :grinning:

 

想了一下,

SPFA的时间复杂度为:$O(ke)$

其中的$k$是平均入队次数,$e$是边数,$k$的值一般稳定在2左右,所以说,当一个点的入队次数大于20的话,十有八九就是出现负环了

当然去了考场上还是乖乖的写dfs的SPFA吧,毕竟到时候可就只有一次机会啊

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:树上倍增求LCA及例题

下一篇:&lt;学习笔记&gt; A*算法求第k短路