设计学习网站,wordpress建立外贸网站,wordpress网站商务通,网站建设高端培训学校正题
题目链接:https://www.luogu.com.cn/problem/P6085 题目大意 nnn个点的一张无向图#xff0c;有kkk条必走边#xff0c;mmm条其他边#xff0c;求从111出发经过必走边后回到起点的最短路径。 2≤n≤13,0≤k≤78,2≤m≤2002\leq n\leq 13,0\leq k\leq 78,2\leq m\leq 2…正题
题目链接:https://www.luogu.com.cn/problem/P6085 题目大意
nnn个点的一张无向图有kkk条必走边mmm条其他边求从111出发经过必走边后回到起点的最短路径。
2≤n≤13,0≤k≤78,2≤m≤2002\leq n\leq 13,0\leq k\leq 78,2\leq m\leq 2002≤n≤13,0≤k≤78,2≤m≤200 解题思路
可以理解为在只包含必走边的图上加若干条其他边使得这张图存在欧拉回路。
欧拉回路要求所有点联通且度数为偶数考虑状态压缩dpdpdp设三进制的状态。
fsf_sfs000表示没有联通111表示度数为奇数222表示度数为偶数。
然后先考虑加点进来的方式也就是加进来的点我们只考虑不是必须的边的部分。而且使用这些点类似于一棵树的连接联通的点。并不是连接成真正的树而是如果使用了不必须的边的话只和一个点联通
然后处理完后再考虑调整图的奇偶性设gSg_SgS表示集合SSS中的点为奇数时调整为偶数的最小代价。
然后用fff和ggg计算答案就好了。
时间复杂度O(3nn2)O(3^nn^2)O(3nn2) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N14;
struct node{int to,next;
}a[N*N];
int n,k,m,tot,ans,sta,st,ls[N],p[N],deg[N];
int dis[N][N],g[1N],f[1594323];
queueint q;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
int main()
{memset(dis,0x3f,sizeof(dis));memset(g,0x3f,sizeof(g));memset(f,0x3f,sizeof(f));scanf(%d%d,n,k);p[0]1;dis[0][0]0;for(int i1;in;i)p[i]p[i-1]*3,dis[i][i]0;for(int i1;ik;i){int x,y,w;scanf(%d%d%d,x,y,w);x--;y--;addl(x,y);addl(y,x);dis[x][y]dis[y][x]min(dis[x][y],w);deg[x];deg[y];sta^(1x)^(1y);answ;}scanf(%d,m);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);x--;y--;dis[x][y]dis[y][x]min(dis[x][y],w);}for(int k0;kn;k)for(int i0;in;i)for(int j0;jn;j)dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);int MS(1n);g[0]0;for(int s0;sMS;s)for(int i0;in;i){if((si)1)continue;for(int ji1;jn;j)if(!((sj)1)){int zs^(1i)^(1j);g[z]min(g[z],g[s]dis[i][j]);}}q.push(2);f[2]0;while(!q.empty()){int sq.front();q.pop();for(int x0;xn;x){if(s/p[x]%3)continue;int tsp[x]*2;for(int ils[x];i;ia[i].next){int ya[i].to;if(!(s/p[y]%3))continue;if(f[t]g[MS])q.push(t);f[t]min(f[t],f[s]);}for(int y0;yn;y){if(!(s/p[y]%3))continue;tsp[x];if((t/p[y]%3)2)t-p[y];else tp[y];if(f[t]g[MS])q.push(t);f[t]min(f[t],f[s]dis[x][y]);}}}int minsg[MS];for(int s0;sp[n];s){bool flag0;int st0;for(int i0;in;i){if((s/p[i]%3)0deg[i]){flag1;break;}if(s/p[i]%3)st|(1i)*(2-s/p[i]%3);}if(flag)continue;st^sta;minsmin(mins,f[s]g[st]);}printf(%d\n,ansmins);return 0;
}
