昨天统计题数错联系锟神时提到了这道题,给他讲了我的思路,感觉博客写的太简略,正好百题之后准备重新理一遍博客,所以就先来写写这道题。
有v个城市,每个城市间都有道路连通,要检查e个道路,起点终点任选。输入v、e、检查每个道路的时间t。求最少总时间。
求最少总时间,感觉与UVa818切锁链中的环有些神似。
所给的e条道路是必经的,只需要找到最少的路使得给的路形成欧拉道路即可。
首先,对所有的道路判连通,假设形成了n个连通组,那么连起来就需要n-1条路。
然后,统计每组中度数为奇数的点,每一个奇数点都要构造另一条路使之度数为偶数,但是每一组仅需形成一条链而不是环,仅需形成欧拉道路而不是欧拉回路,所以统计个数要
减去链的端点2。
最后,求每组的和,减去一就是需要连成一个整体所用的道路数,加上e,总道路就求出来的。
|
|
本文迁移自我的 CSDN博客 ,格式可能有所偏差。