本文共 1743 字,大约阅读时间需要 5 分钟。
You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).
The first line of the input contains two integers n and m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n is the amount of vertices, and m is the amount of edges. Following m lines contain edges as a triples x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y are edge endpoints, and w is the edge length.
Output minimal cycle length or -1 if it doesn't exists.
3 31 2 12 3 13 1 1
3
3 21 2 32 3 4
14
题意:
给出一个无向带权图,问从1号点出发,通过所有的边至少一次,再回到1号点,需要花费的最少代价是多少。存在自环和重边。
如果无法满足上述要求,那么输出-1。
节点数n,边数m。(1 <= n <= 15, 0 <= m <= 2000)
每条边包含3个属性u, v, w, u和v是边的端点,w是通过边的代价。(1 <= x,y <= n, 1 <= w <= 1e4)。
题解:
先跑一次Floyd求出全源最短路,如果1号点到某个点的最短路不存在那么原图不连通,
如果所有点的度数都是偶数,那么存在一条欧拉回路,已经得到结果,
否则存在某些点的度数是奇数,尝试用一些路径连接这些点,只有路径端点的度数奇偶性会发生变化,
可以发现度数已经是偶数的点作为某条路径的端点是不优的,于是考虑dp[S]表示度数是奇数的点集为S时的最小代价,
转移枚举选出两个集合内的点,用一条路连起来,这两个点的度数都会变成偶数,复杂度是O(n^2*2^n),
一个trick是由于最后所有点度数都要是偶数,也就是每个度数是奇数的点都要作为某条路径的端点,
那么每次考虑选出集合内标号最小的点,枚举这个点和另一个点用一条路径连起来,复杂度是O(n*2^n)。
#include#include #include #include #include #include #include using namespace std;#define rep(i,a,n) for (int i=a;i =a;i--)#define pb push_back#define fi first#define se secondtypedef vector VI;typedef long long ll;typedef pair PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=18;int g[maxn][maxn],d[1< 0;j--) { for(int i=0;i
转载地址:https://blog.csdn.net/fouzhe/article/details/56482552 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!