NOIP2018D2T1 旅行

水深无声 2023-06-02 13:59 1阅读 0赞

#include<cstdio>
    #include<set>
    #include<cstring>
    
    int n,m,cnt,mini[500005],ans[500005],u[500005],v[500005];
    
    bool vis[500005];
    
    std::set<int> e[500005];
    
    inline bool cmp(const int *a,const int *b,int now){
        for(int i=1;i<=now;i++){
            if(a[i]<b[i])return true;
            if(a[i]>b[i])return false;
        }
        return true;
    }
    
    inline void dfs(int u){
        vis[u]=1;
        ans[++cnt]=u;
        if(!cmp(ans,mini,cnt))return;
        if(cnt==n){
            for(int i=1;i<=n;i++)mini[i]=ans[i];
        }
        for(std::set<int>::iterator it=e[u].begin();it!=e[u].end();it++){
            int v=*it;
            if(!vis[v]){
                dfs(v);
            }
        }
    }
    
    int main(){
        memset(mini,0x3f,sizeof(mini));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u[i],&v[i]);
            e[u[i]].insert(v[i]);
            e[v[i]].insert(u[i]);
        }
        if(n==m){
            for(int i=1;i<=m;i++){
                if(i>1){
                    e[u[i-1]].insert(v[i-1]);
                    e[v[i-1]].insert(u[i-1]);
                }
                e[u[i]].erase(v[i]);
                e[v[i]].erase(u[i]);
                cnt=0;
                memset(vis,0,sizeof(vis));
                vis[1]=1;
                dfs(1);
            }
        }
        else{
            dfs(1);
        }
        for(int i=1;i<=n;i++){
            printf("%d ",mini[i]);
        }   
    }

转载于:https://www.cnblogs.com/Y15BeTa/p/11570086.html

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关 noip模拟测试18 T2搜索

考试 .....打了个搜索60分下来改了个字母A了，，，，，考试后n个小时当我得知别人的搜索思路后，开始造数据看看自己跑的快不快然后答案错了？？？？考试数据真水

向右看齐/ 2023年10月10日 10:23/ 0 赞/ 50 阅读

相关 D1T3

include<bits/stdc++.h> using namespace std; const int N=500005; struct node{ int pos

冷不防/ 2023年08月17日 15:45/ 0 赞/ 152 阅读

相关【NOIP2012】开车旅行

Description [【NOIP2012】开车旅行][NOIP2012] （题面太长不想描述……） Solution 由于题目很复杂，所以我们将这道题分成三

叁歲伎倆/ 2023年06月05日 08:55/ 0 赞/ 43 阅读

相关 NOIP2018D2T1 旅行

include<cstdio> include<set> include<cstring> int n,m,cnt,mini[5000

水深无声/ 2023年06月02日 13:59/ 0 赞/ 2 阅读

相关 2019.5.25 Noip模拟测试2 T1题解

![1596060-20190525150846294-1346967829.png][] ![1596060-20190525150909316-551704796.png

本是古典何须时尚/ 2021年12月23日 23:57/ 0 赞/ 261 阅读

相关 NOIP2018PJ T3 摆渡车

[题目链接][Link 1] 题意：时间轴上分布着$n$位乘客，$i$号乘客的位置为$t\_i$，用互相距离不小于$m$的车次将时间轴分为若干部分并管辖上一个区

傷城~/ 2021年12月11日 23:32/ 0 赞/ 158 阅读

相关 [NOIP2018 PJ T4]对称二叉树

题目大意：问一棵有根带权二叉树中最大的对称二叉树子树，对称二叉树为需满足将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。题解：在对称二叉树中，对于深

短命女/ 2021年12月09日 21:13/ 0 赞/ 171 阅读

相关 7.18 T1 星际旅行

题意：n个点，m条边，无重边，有自环，要求经过m-2条边两次，2条边一次，问共有多少种本质不同的方案。本质不同：当且仅当至少存在一条边经过次数不同。题解：考试的时候理解错题

小鱼儿/ 2021年11月27日 01:02/ 0 赞/ 273 阅读

相关【NOIP 2018 T3】摆渡车

文章目录前言题目题目描述输入格式输出格式输入输出样例输入1

你的名字/ 2021年11月19日 14:36/ 0 赞/ 218 阅读

相关 NOIP 2015[D1 T3]斗地主（30分的特判）

这个题是大暴搜，然而我只能写一下30分的特判。后来写的搜索:[http://blog.csdn.net/qq\_36820605/article/details/73044

绝地灬酷狼/ 2021年09月29日 03:14/ 0 赞/ 235 阅读