[关闭]
@rebirth1120 2019-11-12T07:46:18.000000Z 字数 2161 阅读 668

[牛客]十二桥问题 解题报告

解题报告


[牛客]十二桥问题

题意

有一张 个点 条边的带权有向图 ,
其中有 条边是一定要经过的 ,

从节点 出发, 求 : 经过了所有必须经过的边之后,又回到节点 的最短路径.

思路

首先, 虽然点的数量比较大, 但是大部分是没用的, 我们只需要关注必须经过的那几条边 (称为桥) 的端点.

所以, 一开始先分别以 节点和所有桥的端点作为起点, 跑若干遍 , 并用这若干个点之间的最短距离建一张新图.

然后, 考虑状压dp, 设 为到了当前点为 , 经过的边集(桥集)为 时的最短路径.

转移时, 对于当前边集中的边的端点, 枚举它们上一次经过了哪条边转移,
由于题目保证整张图联通, 所以新的最短路图是一个完全图, 因此不是当前边集中的边的端点的点的状态是无用的, 不需要转移.

代码

  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define mkp make_pair
  4. using namespace std;
  5. const int N=5e4+7;
  6. const int M=2e5+7;
  7. const int K=12+7;
  8. const int L=4096+7;
  9. int n,m,k,all,poi,num[N],cnt,bdg[2*K][2*K],bi[K],rec[L];
  10. ll f[2*K+1][L],dis[N],mp[2*K+1][2*K+1],ans,inf;
  11. int lst[N],nxt[2*M],to[2*M],tot;
  12. ll len[2*M];
  13. bool b[N];
  14. struct bridge{
  15. int x,y;
  16. ll w;
  17. }e[M];
  18. void add(int x,int y,ll w){
  19. nxt[++tot]=lst[x];
  20. to[tot]=y;
  21. len[tot]=w;
  22. lst[x]=tot;
  23. }
  24. void read(){
  25. cin>>n>>m>>k; num[1]=++cnt; int x,y;
  26. for(int i=1;i<=m;i++){
  27. scanf("%d%d%lld",&x,&y,&e[i].w);
  28. if(!num[x]) num[x]=++cnt;
  29. if(!num[y]) num[y]=++cnt;
  30. x=num[x];
  31. y=num[y];
  32. e[i].x=x;
  33. e[i].y=y;
  34. add(x,y,e[i].w);
  35. add(y,x,e[i].w);
  36. if(i<=k){ bdg[x][y]=bdg[y][x]=i; poi=cnt; }
  37. }
  38. for(int i=1;i<=k;i++){ bi[i]=1<<i-1; rec[bi[i]]=i; }
  39. all=(1<<k)-1;
  40. memset(f,127,sizeof(f));
  41. memset(mp,-1,sizeof(mp));
  42. inf=f[0][0];
  43. }
  44. priority_queue<pair<ll,int> >h;
  45. void dijk(int st){
  46. memset(dis,127,sizeof(dis));
  47. memset(b,0,sizeof(b));
  48. dis[st]=0;
  49. h.push(mkp(0,st));
  50. while(!h.empty()){
  51. int u=h.top().second; h.pop();
  52. if(b[u]) continue;
  53. b[u]=1;
  54. for(int i=lst[u];i;i=nxt[i])
  55. if(dis[to[i]]>dis[u]+len[i]){
  56. dis[to[i]]=dis[u]+len[i];
  57. h.push(mkp(-dis[to[i]],to[i]));
  58. }
  59. }
  60. for(int i=1;i<=2*k+1;i++)
  61. if(dis[i]!=inf) mp[st][i]=dis[i];
  62. }
  63. void print(int x){
  64. for(int i=1;i<=k;i++){
  65. printf("%d",x&1);
  66. x>>=1;
  67. }
  68. }
  69. int main(){
  70. // freopen("bridge.in","r",stdin);
  71. // freopen("bridge.out","w",stdout);
  72. read();
  73. for(int i=1;i<=2*k+1;i++) dijk(i);
  74. f[1][0]=0; h.push(mkp(0,1));
  75. n=poi;
  76. ans=inf;
  77. for(int i=0;i<=all;i++){
  78. for(int j=i;j;j-=j&-j){
  79. int t=rec[j&-j];
  80. int x=e[t].x,y=e[t].y;
  81. for(int v=1;v<=n;v++)
  82. if(f[v][i^bi[t]]!=inf){
  83. f[x][i]=min(f[x][i],f[v][i^bi[t]]+mp[y][v]+e[t].w);
  84. f[y][i]=min(f[y][i],f[v][i^bi[t]]+mp[x][v]+e[t].w);
  85. }
  86. // printf("%d ",x); print(i); printf(": %lld\n",f[x][i]);
  87. // printf("%d ",y); print(i); printf(": %lld\n",f[y][i]);
  88. }
  89. }
  90. for(int i=1;i<=n;i++)
  91. if(f[i][all]!=inf) ans=min(ans,f[i][all]+mp[i][1]);
  92. printf("%lld\n",ans);
  93. return 0;
  94. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注