首页 > 代码库 > CodeForces 21D Traveling Graph 状压dp+欧拉回路
CodeForces 21D Traveling Graph 状压dp+欧拉回路
题目链接:点击打开链接
题意:
给定n个点m条边的无向图
求从1点开始经过每条边至少一次最后回到1点的最小路程
显然就是找一条路径可重复的欧拉回路
思路:
首先对于欧拉回路的结论是:所有点的度数都为偶数
因为所有边至少经过一次,那么可以把题意转换成加最少多少条边使得图满足以上结论
而加的边目的是为了把奇度数转成偶度数,先floyd一下得到任意点间加边的最小花费
dp[i]表示状态i下度数都为偶数的最小花费。
状压dp,把i状态下,所有未选择的点中挑2个奇度数的转移即可。
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <iostream> #include <map> #include <set> #include <math.h> using namespace std; #define ll int #define inf 1000000007 #define N 16 int dis[N][N], n, m; void floyd(){ for(ll k = 0; k < n; k++) for(ll i = 0; i < n; i++) for(ll j = 0; j < n; j++) dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]); for(ll i = 0; i < n; i++)dis[i][i] = 0; } int du[N], ans, dp[1<<N];//dp[i] 表示加边使得i状态下的所有点都是偶度数的最小花费 ll work(){ ll i, j, k; for(i = 1; i < n; i++)//如果i这个点有边连接,但点0又走不到这个点,说明和这个点相连的边是走不到的,即图不连通 if(du[i] && dis[0][i]==inf)return -1; ll all = (1<<n)-1; for(i = 0; i <= all; i++) dp[i] = inf; dp[0] = 0; for(k = 0; k <= all; k++) { for(i = 0; i < n; i++)//找到一个奇度数的点i if((du[i]&1) && (k&(1<<i)))break; if(i==n)dp[k] = 0; for(i = 0; i < n; i++)// 枚举奇数度点i if((du[i]&1) && !(k&(1<<i))) for(j = i+1; j < n; j++)// 枚举奇数度点j if((du[j]&1) && !(k&(1<<j)) && dis[i][j]<inf) dp[k|(1<<i)|(1<<j)] = min(dp[k|(1<<i)|(1<<j)],dp[k]+dis[i][j]); } if(dp[all]>=inf)return -1; return ans + dp[all]; } int main(){ ll i, j, u, v, w; while(cin>>n>>m){ for(i=0;i<n;i++)for(j=0;j<n;j++)dis[i][j] = inf; memset(du, 0, sizeof du); ans = 0; while(m--){ cin>>u>>v>>w; u--; v--; dis[u][v] = dis[v][u] = min(dis[u][v], w); du[u]++; du[v]++; ans += w; } floyd(); cout<<work()<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。