UVa 12,118 检查员难题 Inspector’s Dilemma
发布时间
阅读量：
阅读量
某国家共有V个城镇，任意两个城镇间均存在一条双向道路，其长度为T，现需找出一条最短路径，该路径需包含E条边。
无向图中欧拉路径的判定问题；
首先判断图中存在多少个不连通的子图集合。
对于每个独立的子图集合，均可通过欧拉路径的相关条件进行分析。
具体而言，整个图中最多仅允许存在两个度数为奇数的顶点。
而超出该限制的奇数度顶点数量除以2，即为需要额外添加的路径数目。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
int p[1100];
unordered_map<int, int> m;
//并查集
void init() {
for (int i = 0; i < 26; i++)
p[i] = i;
}
int find(int a) {
while (a != p[a])
a = p[a];
return a;
}
void merge(int a, int b) {
int c = find(a);
int d = find(b);
if (c != 全部评论 (0)
还没有任何评论哟~