#P18947. [Mladen Manev 2021 A3] tours / 混合图中的往返路线
[Mladen Manev 2021 A3] tours / 混合图中的往返路线
混合图中的往返路线
一个混合图有 个顶点、 条边。每条边是有向边或无向边,无自环,允许重边。
对于每个询问 ,判断是否能选取一条 的路线和一条 的路线,使这两条路线对每条无向边至多使用其中一个方向。路线可以重复经过边,但同一条无向边不能在本次往返中被双向使用。有向边只能按规定方向使用。
不同询问互相独立。等价地,每个询问分别判断:是否存在对所有无向边的某种定向,使 处于同一个强连通分量。
输入格式
第一行 。接下来 行,每行 ; 表示无向边 , 表示有向边 。
随后一行 ;接下来 行,每行两个不同顶点 。
输出格式
一行连续的 个字符,每个字符为 1 或 0,分别表示对应询问可行或不可行。字符间不加空格。
数据范围
,,顶点编号为 至 。
示例
3 3
2 1 2
1 2 3
2 3 1
2
1 3
2 3
11
此处为整理者补充的简短示例。官方原始示例见附带 PDF。
来源与数据说明
2021 年 Dr. Mladen Manev,A3,原题名 tours。赛事资料,原文题面见附件 statement.pdf。
原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。