站外题求调,玄关
  • 板块学术版
  • 楼主RainySoul
  • 当前回复1
  • 已保存回复2
  • 发布时间2024/8/31 09:18
  • 上次更新2024/8/31 12:47:46
查看原帖
站外题求调,玄关
654577
RainySoul楼主2024/8/31 09:18

题面:

给定一个 nn 个点 mm 条边的简单无向图,求在图中最多可选出的不同的长度为 2 的简单路径数量,使得每条边至多属于 1 条路径。并给出构造。

输入格式

第一行两个正整数 nn, mm。 接下来 mm 行,每行两个正整数 uiu_i, viv_i,表示 (uiu_i, viv_i) 之间有一条无向边。

输出格式

第一行一个非负整数 TT 表示最多可选出的路径数量。

接下来 TT 行,每行三个互不相等的正整数 uu, vv, ww 表示一条由 uu 到 ww,包含无向边 (uu, vv), (vv, ww) 的路径。

你需要确保每一条边至多被包含一次。如有多种构造方案,输出任意一种。

2024/8/31 09:18
加载中...