【题解】LuoGu5022/NOIp2018:旅行

原题传送门
考场里被自己实实在在的坑了一发,竟然没发现n、m小于5000!
结果我一直在那想O(nlogn)的做法,今天尝试O(n^2)暴力
考场里打了 m = n − 1 m=n-1 m=n1 60分的部分,还是O(nlogn)的,代码就不放了,不好意思

首先还是想 m = n − 1 m=n-1 m=n1的情况,不用去想倒退这个动作,其实整个过程就是遍历一棵树,字典序最小当然就以1为根,在自己的儿子中从小到大依次遍历,遍历途中记录点即可

m = n m=n m=n的情况其实就是一颗基环树,发现最终还是只跑了(n-1)条边,另一条边是跑不到的,所以暴力枚举删边,每次删边就是化归到 m = n − 1 m=n-1 m=n1的情况来做

那么,怎么才能在儿子中从小到大遍历呢,其实很简单,开始先用邻接矩阵存储,然后想想链式前向星存储特点,越后加入的边到时候提取的时候越先提取,所以只要对于每个点,从大到小枚举儿子链前加边即可

至于删边后联不联通的问题,可以开一个vis数组,因为若删边不联通,则图上必有环,而vis阻断环上的无限遍历

Code:

#include <bits/stdc++.h>
#define maxn 5010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
struct Line{
	int x, y;
}line[maxn];
int head[maxn], num, cnt, s[maxn], ans[maxn], Map[maxn][maxn], n, m, vis[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void add_edge(int x, int y){ edge[++num].to = y; edge[num].next = head[x]; head[x] = num; }

bool check(){
	if (cnt < n) return 0;
	for (int i = 1; i <= n; ++i) if (s[i] < ans[i]) return 1; else if (s[i] > ans[i]) return 0;
	return 0;
}

void dfs(int u){
	vis[u] = 1; s[++cnt] = u;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (Map[u][v] && !vis[v]) dfs(v);
	}
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read();
		line[i].x = x, line[i].y = y;//把边存起来,以备删边之用
		Map[x][y] = Map[y][x] = 1;//邻接矩阵存图
	}
	for (int i = 1; i <= n; ++i)
		for (int j = n; j; --j) if (Map[i][j]) add_edge(i, j);//从大到小枚举加边
	ans[1] = n + 1;//ans一开始赋大值
	if (m < n){
		dfs(1);
		for (int i = 1; i <= n; ++i) printf("%d ", s[i]);
	} else{
		for (int i = 1; i <= m; ++i){
			Map[line[i].x][line[i].y] = Map[line[i].y][line[i].x] = 0;//删边
			memset(vis, 0, sizeof(vis));//不要忘了这步
			cnt = 0; dfs(1);
			if (check()) for (int j = 1; j <= n; ++j) ans[j] = s[j];//更新答案
			Map[line[i].x][line[i].y] = Map[line[i].y][line[i].x] = 1;//恢复
		}
		for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
	}
	return 0;
}
NOIP竞赛学习材料清单可以包含以下内容: 1. 编程基础知识书籍:包括《算法竞赛入门经典》、《挑战程序设计竞赛》等书籍,通过学习这些书籍可以掌握基本的编程算法和数据结构知识。 2. 高级编程语言教材:选择一种常用的编程语言,如C++、Python等,学习该语言的语法和常用函数,掌握编程技巧。 3. 题目解析和解题技巧指南:选择一些NOIP中经典的题目解析和解题技巧指南,如《NOIP竞赛算法指南》等,这样可以帮助理解题目要求和解题思路,提高解题能力。 4. 网络资源:可以通过参加NOIP的官方论坛、博客和社交媒体等平台,了解最新的竞赛信息和刷题经验享,跟随优秀选手的博客或微博进行学习、交流。 5. 备战训练营和竞赛模拟题:参加NOIP竞赛前,可以参加一些备战训练营或报名参加模拟题训练,这样可以熟悉竞赛环境和题型,提前适应竞赛节奏。 6. 在线编程平台:通过在在线编程平台上刷题,如LUOGU、Codeforces等,可以提高编程算法和思维能力,熟悉各种题型,掌握解题技巧。 7. 经典题目集:收集一些经典的NOIP竞赛题目集合,如《NOIP历年试题》等,通过做这些题目可以了解历年的考点和难度布,熟悉竞赛的题目类型和题解。 8. 学习资料的整理和总结:将学习过程中的笔记、代码和解题思路进行整理和总结,形成自己的学习资料,方便查阅和复习。 通过以上学习材料的学习和积累,可以提高编程算法和思维能力,提高在NOIP竞赛中的表现。
评论 1
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值