almost 2 years ago

前言

好神的题目啊...

题目大意

给定一张个点条边的无向图,你需要选择一个颜色种类数,然后用这种颜色给每条边染色,要求对于图中任意一个简单环,每种颜色的边的数量都相同,求所有可行的

分析

首先我们发现原图中的桥肯定是不影响答案的,因此一发,考虑每个双连通分量。
考虑定义同类的边,边的同类边定义为删去后图中的桥,我们发现同类边要么全部出现在简单环上,要么全部没有。
设每组同类边的个数集合为,那么答案就是,感性理解一下是对的,并不太清楚怎么证明QAQ
tour.cpp

← CC MONOPLOY 2016-7-7 模拟题 →
 
comments powered by Disqus