返回信息流就是一个手游的大模拟，求问这个题大概可以达到什么难度？校赛？网预？
或者说有没有什么问题？
有没有什么算法可以高效解决呢？
Problem Description
Senior Mengchun likes playing a game named “One Touch Drawing” on her mobile phone.In this game,player should visit each edge of a graph. In the lesson Discrete Mathematics we know, the graph which has an Eulerian path can be one-touch-drawed. But this time she is confused,because the graph is not just an ordinary undirected graph,and there are some special vertexes and edges as listed below:
1. Pink edges: you should visit every pink edges twice.
2. Narrowed edges:you MUST visit it from first vertex to the second one,but still once.
3. Narrowed pink edges: you MUST visit it from first vertex to the second one twice.
4. Yellow vertexes:There are at most two yellow vertexes in the graph.If you visit one of them,you will jump to another one immediately,and vice versa.
Input
The first line contains two integers N and M,indicating the number of vertexes and edges of the undirected graph.(N<=10^2,M<=10^3)
Next M lines,each line contains three integers X,Y,C. X and Y indicate the number of vertex,C means the type of edge: 0 for common edge,1 for pink edge,2 for narrowed edge(meaning you must visit it from vertex X to vertex Y),3 for narrowed pink edge.
Next one line contains an integer,only 0 and 2 are accepted,indicating the number of yellow vertexes.If 2 is inputed,you should add one line containing two integers,indicating the two yellow vertexes.
Output
Output the sequence of vertexes you should visited,separated by space.
If the graph has no solution,output -1.
If the graph has more than one solution,output the least lexicographicalorder one.
Sample Input
12 18
1 2 0
2 3 0
1 4 0
2 5 0
2 6 0
4 5 3
5 6 0
7 5 2
6 8 2
4 10 0
7 8 0
8 9 3
3 9 0
7 11 0
8 11 0
10 11 0
11 12 0
9 12 0
2
6 7
Sample Output
8 7 6 8 9 3 2 1 4 5 2 6 7 5 6 7 11 8 9 12 11 10 4 5
//因为之前的数据是乱写的。。。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #90475同步于 2016/7/20
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[问题]求问一个算法题，大概是什么难度？
lhy963
2016/7/20镜像同步13 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
混合图欧拉回路
前三种就是正常的加边，加重边
对于最后一种yellow vertex来说，看起来可以往两个点直接多加几条边，然后在构造的解里删掉的样子
好难啊- -
这个数据量应该不算难，只有100个点的话dfs不是就可以了
然后。。不是说字典序最小的解吗？这个比示例的解字典序小吧？
8 7 6 8 9 3 2 1 4 5 2 6 7 5 6 7 11 8 9 12 11 10 4 5
比示例小的，还有30个。。
【 在 lhy963 的大作中提到: 】
: 就是一个手游的大模拟，求问这个题大概可以达到什么难度？校赛？网预？
: 或者说有没有什么问题？
: 有没有什么算法可以高效解决呢？
: ...................
因为这道题是LZ编的。。。所以示例数据和范围是我乱写的。。。因为还没写标程。。。
出题的原因是因为某新大一学妹在玩一笔画手游 我就说我送你道题 希望你在大学期间做出来
但似乎看来有点难为萌新了。。。
【 在 liyi5133 的大作中提到: 】
: 这个数据量应该不算难，只有100个点的话dfs不是就可以了
: 然后。。不是说字典序最小的解吗？这个比示例的解字典序小吧？
: 8 7 6 8 9 3 2 1 4 5 2 6 7 5 6 7 11 8 9 12 11 10 4 5
: ...................
如果是把两个黄色的点捏到一起呢？
in addition 这个是求欧拉通路 不一定是回路
【 在 winoros 的大作中提到: 】
: 混合图欧拉回路
: 前三种就是正常的加边，加重边
: 对于最后一种yellow vertex来说，看起来可以往两个点直接多加几条边，然后在构造的解里删掉的样子
: ...................
哈原来是这样。大一萌新以前如果学过信息学竞赛应该问题不大，纯新手的话大一确实有点难。
不过题主都说了大学期间嘛，这个至少1000个点dfs我觉得不难，不知道图论有没有简便的方法。
【 在 lhy963 的大作中提到: 】
: 因为这道题是LZ编的。。。所以示例数据和范围是我乱写的。。。因为还没写标程。。。
:
: 出题的原因是因为某新大一学妹在玩一笔画手游 我就说我送你道题 希望你在大学期间做出来
:
: 但似乎看来有
: .........
发自「贵邮」
必然是没学过信息竞赛啦~~~~人家报的城市规划被我劝成计科了~~而且并非报考的北邮而是某普通一本~~
只是她好奇大学风格的题是什么样的 我就把一笔画手游用acm的风格编成一道题
查了一下图论上的解法跟网络流有关系，写普通的dfs反正把他那手游玩通关没问题（游戏里最多几百条边）
【 在 liyi5133 的大作中提到: 】
: 哈原来是这样。大一萌新以前如果学过信息学竞赛应该问题不大，纯新手的话大一确实有点难。
: 不过题主都说了大学期间嘛，这个至少1000个点dfs我觉得不难，不知道图论有没有简便的方法。
:
: ...................
path和circuit的存在性判定差不多
黄色点不能捏到一起啊，边不等价的
【 在 lhy963 的大作中提到: 】
: 如果是把两个黄色的点捏到一起呢？
: in addition 这个是求欧拉通路 不一定是回路
混合图用dfs o(n)根本做不了的啊。。。几百条边拿命搜么- -
【 在 lhy963 的大作中提到: 】
: 必然是没学过信息竞赛啦~~~~人家报的城市规划被我劝成计科了~~而且并非报考的北邮而是某普通一本~~
: 只是她好奇大学风格的题是什么样的 我就把一笔画手游用acm的风格编成一道题
: 查了一下图论上的解法跟网络流有关系，写普通的dfs反正把他那手游玩通关没问题（游戏里最多几百条边）
: ...................
实际上的图大都是很稀疏的啊，几百条边也不会要全排列，都是沿着相邻的去扩展的，有效情况远没有那么夸张。说不定还可以剪枝优化。
以前课程作业做过一次网页关联分析的，处理后有14w的节点，270w条边，半秒就跑完了。当然方法和具体的问题有关，不试一试怎么知道呢。
【 在 winoros 的大作中提到: 】
: 混合图用dfs o(n)根本做不了的啊。。。几百条边拿命搜么- -
: 【 在 lhy963 的大作中提到: 】
: : 必然是没学过信息竞赛啦~~~~人家报的城市规划被我劝成计科了~~而且并非报考的
: .........
发自「贵邮」