[LLL邀请赛]参观路线(图论+dfs)

emmmm....学校的oj被查水表了,扒不到原题面,所以....

但是我还是扒到了题面。。。

[LLL邀请赛]参观路线(图论+dfs)

题目大意:给定一个完全图,删掉其中一些边,然后求其字典序最小的遍历顺序

有点像去年day2T1啊....

但是数据范围如果建图的话就可以螺旋升天了。

很容易想到建反图(郑州集训233,可是这题不建反图会死)

然后想怎么遍历....

dfs序无疑,但是该怎么....跑这么多呢....

(真的很难想)

solution:

删边。

可以说删边。

既然要求字典序最小,那就给它一个字典序最小:123456789

把所有点先连上,向下跑,判断这两点之间的路有没有被炸掉,要是被炸掉了,就跑到i+2那个点去,然后把路删了,连到下面去。

有些坑人,代码细节不少。

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define rg register
using namespace std;
inline int read()//怕被卡加的读优
{
int x=,f=;char s=getchar();
while(s>''||s<''){if(s=='-')f=-;s=getchar();}
while(s<=''&&s>=''){x=x*+s-'';s=getchar();}
return x*f;
}
const int maxn=;
int n,m;
vector < int > g[maxn];//无权图用vector存方便
int nxt[maxn];//学校oj卡关键字太狠了
int to[maxn];//辅助删边数组
void dfs(int u)
{
printf("%d\n",u);//走一个输出一个
sort(g[u].begin(),g[u].end());//对炸掉的点排序,方便下面二分查找
nxt[to[u]]=nxt[u];//删边
to[nxt[u]]=to[u];
for(rg int i=nxt[];i<=n;i=nxt[i])
{
if(i!=g[u][lower_bound(g[u].begin(),g[u].end(),i)-g[u].begin()])//找不找得到一个被炸的点与自己相同
{
dfs(i);//向下搜
return;//老子不搜了
}
}
} int main()
{
n=read();m=read();
for(rg int i=;i<=n;i++)
{
nxt[i]=i+;//连一个字典序最小数组
to[i]=i-;//辅助
g[i].push_back();//注意了,如果一个vector里是空的的话,那么sort啊,lower_bound会出事,所以放进去一个无限大
}
nxt[]=; to[]=;
for(rg int i=;i<=m;i++)
{
int x,y;
x=read();y=read();//scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);//建反图
}
dfs();//字典序最小,肯定是从1开头最小
return ;
}
上一篇:redis解决商品秒杀问题


下一篇:BZOJ1299[LLH邀请赛]巧克力棒——Nim游戏+搜索