ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

ICPC澳门 K - Link-Cut Tree(图论 + dfs + 并查集)

2022年4月3日 672点热度 0人点赞 0条评论

题目传送门:K-Link-Cut Tree_第46屆ICPC 東亞洲區域賽(澳門)(正式賽) (nowcoder.com)

题目大意

有T个测试样例。

给定n个点,m条边,第i条边的权值为2的i次方,求图中权值之和最小的环的边的编号(从小到大)。

思路

看到2的i次方,不难想到用贪心,从小到大(也就是按照输入顺序)遍历所有边,一旦出现环,就直接输出这个环的边的编号就行了,一定是权值和最小的。

这里可以用并查集判断是否有环,方法是如果新的边{x, y}已经相连那么连接之后就会形成第一个环,然后忽略后面的输入,再用dfs配合栈来将环输出。

注意:这题十分毒瘤,我的root函数用while循环来写就TLE了(进行了路径压缩),但是用递归方式写就不会T,真的无语了。

代码

#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define fi first
#define se second
using namespace std;

inline int readInt()
{
     int s = 0,w = 1;char ch = getchar();
     while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
     while('0' <= ch && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
     return s * w;
}

typedef pair<int, int> PII;
const int maxn = 1e5 + 10;
int pre[maxn];

vector<pair<int, int> > g[maxn];

int root(int x)
{
     if(pre[x] == x)return x;
     return pre[x] = root(pre[x]);
}

int stk[maxn], top = 0;
bitset<maxn> vis;

void dfs(int ed, int x, int fa) 
{
    vis[x] = true;
    if(ed == x) 
    {
        sort(stk + 1, stk + top + 1);
        for (int i = 1; i <= top; ++i)
            printf("%d%c", stk[i], i == top ? '\n' : ' ');
    }
    for(auto i : g[x])
     {
        int y = i.fi, id = i.se;
        if (y == fa || vis[y])continue;
        stk[++top] = id;
        dfs(ed, y, x);
        --top;
    }
}

void solve()
{
     int n = readInt(), m = readInt();
     for(int i = 1;i <= n; ++ i)
     {
          pre[i] = i;
          g[i].clear();
          vis[i] = 0;
     }
     int st = 0;//起始点 
     bool tag = 0;//已经有环 
     for(int i = 1;i <= m; ++ i)
     {
          int x = readInt(), y = readInt();
          if(tag)continue;
          g[x].pb({y, i});
          g[y].pb({x, i});
          if(root(x) == root(y))
          {
               st = x;
               tag = 1;
          }
          pre[root(x)] = root(y);
     }
     if(tag)
     {
          top = 0;
          for(auto i : g[st])
          {
               stk[++ top] = i.se;
               dfs(st, i.fi, st);
               -- top;
          }
     }
     else printf("-1\n");
}

signed main()
{
     int T = readInt();
     while(T --)solve();
     return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ dfs icpc 图论 并查集 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号