一个例子教你如何与出题人斗智斗勇
2018-06-17 21:36:21来源：未知 阅读 ()
我以前出过一道题，卡了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及例题
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架：gevent 2020-06-05
- 分享一个自己项目中用到的c++版的日志类(对初学者十分有用的 2020-05-22
- C++ 单独编译 2020-05-10
- 图 2020-05-02
- STL之map 2020-04-27
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
