C. DFS Trees
https://codeforces.ml/contest/1707/problem/C
题意
\(findMST(i)\) 代表从点i开始,按照一下算法,生成的生成树(不一定是最小生成树)。
问i取1~n,findMST(i)是否是最小生成树 输出01串,0代表不行 1代表行。边权按边的顺序从1-n赋值。
思路
首先确定一点,最小生成树是唯一确定的,因为每条边都不相同。
如果一条边(u,v)不是最小生成数上的一边,那么从u到v的路径上的所有点的子树上的点都不可能生成最小生成树(处u, v外)。
具体做法:
1.用prime算法(其他也行)找到那颗最小生成树
2.记录路径(u, v) 树上差分
如果u v(假设u比v深)的lca(u, v) == v 那么就让u的价值-1 v的在路径上的儿子的价值+1
如果lca(u, v) 是两个点外的一个的 那么该lca的价值+1 u v的价值都-1
最后跑一个dfs 每次父亲的价值加给儿子 如果当前节点的价值不为零就代表这个点出发不能生成最小生成树。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n, m, vis[N], fa[N], ans[N], val[N];
vector<int>g[N];
vector<pair<int, pair<int, int>>>e;
ll f[N][32], is[N], dep[N];
void dfs(ll x, ll pre, ll d)//找到每个节点父亲与深度
{
f[x][0] = pre;
dep[x] = d;
for (auto to : g[x])
if (to != pre)
dfs(to, x, d + 1);
}
pair<ll, ll> lca(ll u, ll v)
{
if (dep[u] > dep[v])
swap(u, v);
ll temp = dep[v] - dep[u] - 1;
for (ll i = 0; ((1ll << i) <= temp); i++)//将u v移到同一深度
{
if ((1ll << i) & temp) {
v = f[v][i];
}
}
if (u == f[v][0]) return { v, f[v][0] };
v = f[v][0];
for (ll i = log2(n); i >= 0; i--)//两个节点一起往上走
{ //最多合法的跳跃是 2 ^ log2(n)
if (f[u][i] != f[v][i])//如果相同则代表跳的太多了
{
u = f[u][i];
v = f[v][i];
}
}
return { u, f[u][0] };
}
void init()
{
dfs(1, -1, 0);
for (ll j = 0; (1ll << j) <= n; j++)//预处理出每个节点往上走2^j所到的节点,超过根节点记为-1
{
for (ll i = 1; i <= n; i++)
{
if (f[i][j] < 0)
f[i][j + 1] = -1;
else
f[i][j + 1] = f[f[i][j]][j];
}
}
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void getmst() {
for (auto x : e) {
int u = x.second.first;
int v = x.second.second;
int w = x.first;
u = find(u);
v = find(v);
if (u != v) {
fa[u] = v;
vis[w] = 1;
}
}
}
void dfs2(int x, int fa) {
ans[x] = 1;
if (val[x]) ans[x] = 0;
for (auto to : g[x]) {
if (to == fa) continue;
val[to] += val[x];
dfs2(to, x);
}
}
void solve()
{
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
e.push_back({ i, {u, v} });
}
for (int i = 1; i <= n; i++) fa[i] = i;
sort(e.begin(), e.end());
getmst();
int root = 1;
for (auto x : e) {
int u = x.second.first;
int v = x.second.second;
int w = x.first;
if (vis[w]){
g[u].push_back(v);
g[v].push_back(u);
}
}
init();
for (auto x : e) {
int u = x.second.first;
int v = x.second.second;
int w = x.first;
if (!vis[w]) {
auto [lc1, lc2] = lca(u, v);
if (lc2 == u || lc2 == v) {
if (dep[u] > dep[v]) swap(u, v);
val[v]--;
val[lc1]++;
}
else {
val[u]--;
val[v]--;
val[1]++;
}
}
}
dfs2(1, -1);
for (int i = 1; i <= n; i++)
cout << ans[i];
cout << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _t = 1;
//cin >> _t;
while (_t--)
solve();
return 0;
}
原文地址:http://www.cnblogs.com/yaqu-qxyq/p/16875128.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性