自建网站的步骤,广告软文外链平台,工作人员否认陈道明演庆余年2,深圳企业公司网站设计题目连接#xff1a;https://www.luogu.org/problemnew/show/P5022 \(NOIP2018 DAY2T1\) 考场上只写了60分#xff0c;很容易想到当 m n - 1 时的树的做法。 读题推一下样例不难发现#xff0c;如果选择一个分支节点就必须走到头——直到一个节点没有子树。 那么我们就可以…题目连接https://www.luogu.org/problemnew/show/P5022 \(NOIP2018 DAY2T1\) 考场上只写了60分很容易想到当 m n - 1 时的树的做法。 读题推一下样例不难发现如果选择一个分支节点就必须走到头——直到一个节点没有子树。 那么我们就可以贪心的求得最小字典序序列每次选择节点编号最小的走。 即对当前节点的所有子节点排序选择最小编号的往下进行即可。 60分code #include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
const int maxn 5010;
struct edge{int to, next;
}e[maxn2];
int head[maxn], cnt, n, m;
bool vis[maxn];
void add(int u, int v)
{e[cnt].to v; e[cnt].next head[u]; head[u] cnt;
}
void dfs(int x)
{if(vis[x]) return;vis[x] 1;printf(%d ,x);int a[maxn], num 0;for(int i 1; i n; i) a[i] 0;for(int i head[x]; i ! -1; i e[i].next)a[num] e[i].to;sort(a1, a1num);for(int i 1; i num; i)dfs(a[i]);
}
int main()
{memset(head, -1, sizeof(head));scanf(%d%d,n,m);for(int i 1; i m; i){int u, v;scanf(%d%d,u,v);add(u, v);add(v, u);}dfs(1);return 0;
} 100分做法 考虑 m n 这个情况树多加一条边无自环重边情况下会变成一个环套树。 环套树有一个性质是删去环上的一边就会成为一棵树。 那么当是一棵树的时候我们能找到一个最优解当 m n 时我们就可以找出多棵树的最优解在这些最优解中选取一个最优的最优解就是 m n 时的最优解。 所以我们只需要把这多棵树的最优解找出来就行了。 所以我们需要把环上的边枚举断掉使原图成为一棵树再进行60分的做法。 考虑数据范围5000N^2暴力断边即可。 code #include vector
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
const int maxn 5010;
struct edge{int to, next;
}e[maxn2];
int head[maxn], cnt, n, m, u[maxn], v[maxn];
bool vis[maxn];
void add(int u, int v)
{e[cnt].to v; e[cnt].next head[u]; head[u] cnt;
}
void dfs(int x)
{if(vis[x]) return;vis[x] 1;printf(%d ,x);int a[maxn], num 0;for(int i 1; i n; i) a[i] 0;for(int i head[x]; i ! -1; i e[i].next)a[num] e[i].to;sort(a1, a1num);for(int i 1; i num; i)dfs(a[i]);
}
//
vectorint E[maxn];
int ANS[maxn], NOW[maxn], TOT, CUTu, CUTv;
bool VIS[maxn];
void DFS(int x)
{if(VIS[x]) return;VIS[x] 1;NOW[TOT] x;for(int i 0; i E[x].size(); i){int y E[x][i];if((y CUTv x CUTu) || (x CUTv y CUTu)) continue;DFS(y);}
}
bool check()
{for(int i 1; i n; i){if(ANS[i] NOW[i]) continue;if(ANS[i] NOW[i]) return 1;if(ANS[i] NOW[i]) return 0;}
}
int main()
{memset(head, -1, sizeof(head));scanf(%d%d,n,m);for(int i 1; i m; i){scanf(%d%d,u[i],v[i]);add(u[i], v[i]);add(v[i], u[i]);E[u[i]].push_back(v[i]);E[v[i]].push_back(u[i]);}for(int i 1; i n; i) sort(E[i].begin(), E[i].end());if(m n-1){dfs(1);return 0;}else{for(int i 1; i m; i){TOT 0, CUTu u[i], CUTv v[i];memset(VIS, 0, sizeof(VIS));DFS(1);if(TOT n){if(ANS[1] 0){for(int j 1; j n; j)ANS[j] NOW[j];}else if(check()){for(int j 1; j n; j)ANS[j] NOW[j];}}}for(int i 1; i n; i)printf(%d ,ANS[i]);return 0;}
} 后记 半退役选手回来的第二篇题解。 想想去年自己距离省一线差了10分即使过去半年心里也依旧不是滋味。 DAY2考时想不起环套树来考后出考场的一刹那就想到了可以N^2暴力断边。 其实环套树考前是讲过的断边操作也是老师提到过的。 可是自己却总觉得环套树在NOIP比较冷门吧也没怎么去巩固练习。 可事后再去后悔再去抱怨终究是一点用都没有的。 转载于:https://www.cnblogs.com/MisakaAzusa/p/11002522.html
