洛谷: 传送门 https://www.luogu.org/problemnew/show/P5304
bzoj: 传送门 https://vjudge.net/problem/HYSBZ-5506
参考资料:
[1]:
[2]: http://www.cnblogs.com/cjyyb/p/10736124.html
题意:
一个图 n 个点 m 条边, 里面有 k 个特殊点, 问这 k 个点之间两两最短路的最小值是多少?
之所以做这道题, 是因为早晨的时候, 做 CF 的这道题(戳这里 https://codeforces.com/contest/1146/problem/C ), 题意都木有读懂(??), 然后, 搜了一篇博客(戳这里 http://www.mamicode.com/info-detail-2663849.html );
博主提到了这道题和 "GXOI2019 旅行者" 基本类似, 又说了一个之前从未见到过的名词 "二进制分组",so, 就补了补这道题;
博文 [1] 思路(额外增加了些我的解释):
定义集合 K 中的元素为特殊的 k 个点;
假设我们把特殊点分成 A,B 两个集合: A={a1,a2,....,ax},B={b1,b2,....,by};
保证 ai ∈ A , bi ∈ B,ai ∈ K,bi ∈ K , 且 A∩B = null,x+y = k;
新建节点 s 连向 A 集合的所有点, 新增加的边权为 0;
新建节点 t ,B 集合里的所有点连向 节点 t, 新增加的边权为 0;
那么 s 到 t 的最短路就是 A,B 集合点之间的最短路的最小值.
那么对于 k 个特殊点, 我们枚举二进制里的第 i 位, 把二进制第 i 位为 0 的点放在集合 A 中, 为的点放在集合 B 中 , 用以上方法跑一个最短路.
然后跑 logn 次最短路之后, 所有最短路的最小值就是最终答案.
原理是, 假设 k 个特殊点里最近的是 x 和 y , 那么 x 和 y 一定有一个二进制位不一样;
那么他们肯定在那次分组的时候被放进了不同的集合, 从而肯定被算进了最后的答案之中最短路.
AC 代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<queue>
- using namespace std;
- #define ll long long
- #define INFll 0x3f3f3f3f3f3f3f3f
- #define mem(a,b) memset(a,b,sizeof(a))
- const int maxn=1e5+50;
- int n,m,k;
- int tourist[maxn];
- int num;
- int head[maxn];
- int curNum;
- int curHead[maxn];
- struct Edge
- {
- int to;
- ll w;
- int next;
- }G[maxn*7];
- void addEdge(int u,int v,ll w)
- {
- G[num]={v,w,head[u]};
- head[u]=num++;
- }
- struct Dij
- {
- struct Heap
- {
- int u;
- ll w;
- bool operator <(const Heap& obj) const
- {
- return w> obj.w;
- }
- };
- priority_queue<Heap>q;
- ll dist[maxn];
- bool vis[maxn];
- void dij(int s)
- {
- while(!q.empty())
- q.pop();
- mem(vis,false);
- for(int i=0;i <maxn;++i)
- dist[i]=INFll;
- dist[s]=0;
- q.push({s,0});
- while(!q.empty())
- {
- Heap tmp=q.top();
- int u=tmp.u;
- ll w=tmp.w;
- q.pop();
- if(vis[u])
- continue;
- vis[u]=true;
- for(int i=head[u];~i;i=G[i].next)
- {
- int v=G[i].to;
- ll w=G[i].w;
- if(!vis[v] && dist[v]> dist[u]+w)
- {
- dist[v]=dist[u]+w;
- q.push({v,dist[v]});
- }
- }
- }
- }
- }_dij;
- void Debug()
- {
- for(int i=1;i <= n+2;++i)
- {
- printf("%d:",i);
- for(int j=head[i];~j;j=G[j].next)
- printf("->%d",G[j].to);
- printf("\n");
- }
- }
- /**
- 后来的加边操作会改变某些节点 i 的 head[i]
- 在执行下一次加边指令前要将其修改回来
- 不然, 会出错
- */
- void initHead()// 初始化 head[i],num
- {
- for(int i=1;i <= n;++i)
- head[i]=curHead[i];
- head[n+1]=-1;
- head[n+2]=-1;
- num=curNum;
- }
- ll Solve()
- {
- ll ans=INFll;
- int s=n+1;
- int t=n+2;
- for(int i=0;(1<<i) <= n;++i)
- {
- initHead();
- for(int j=1;j <= k;++j)
- if(tourist[j]&(1<<i))// 第 i 为为 1 的放入集合 A
- addEdge(s,tourist[j],0);
- else// 第 i 为为 0 的放入集合 B
- addEdge(tourist[j],t,0);
- _dij.dij(s);
- ans=min(ans,_dij.dist[t]);
- initHead();
- for(int j=1;j <= k;++j)
- if(tourist[j]&(1<<i))// 第 i 为为 1 的放入集合 B
- addEdge(tourist[j],t,0);
- else// 第 i 为为 0 的放入集合 A
- addEdge(s,tourist[j],0);
- _dij.dij(s);
- ans=min(ans,_dij.dist[t]);
- }
- return ans;
- }
- void Init()
- {
- num=0;
- mem(head,-1);
- }
- int main()
- {
- // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
- int test;
- while(~scanf("%d",&test))
- {
- while(test--)
- {
- Init();
- scanf("%d%d%d",&n,&m,&k);
- for(int i=1;i <= m;++i)
- {
- int x,y,z;
- scanf("%d%d%d",&x,&y,&z);
- addEdge(x,y,z);
- }
- curNum=num;// 记录初始的 num
- for(int i=1;i <= n;++i)
- curHead[i]=head[i];// 记录节点 i 初始指向的 head[i]
- for(int i=1;i <= k;++i)
- scanf("%d",tourist+i);
- printf("%lld\n",Solve());
- }
- }
- return 0;
- }
- View Code
在洛谷上提交这种思路的代码, 需要使用 O2 优化, 不然, 会有 TLE 的点;
在 bzoj 上提交是直接 AC 的;
博文 [2] 思路:
跑两遍 Dij 算法:
第一遍按照输入边的顺序, 定义变量 dis[],pre[];
dis[u]: 到达节点 u 的最短距离;
pre[u]: 使得 dis[u]最短的节点(路径记录, 记的是集合 K 中的节点);
初始, dis[ K ] = 0,pre[ K ]=K;
对于 u->v 这条边, 如果节点 u 更新了节点 v, 那么 pre[v]=pre[u];
第二遍将输入的边反向, 定义变量 disR[],preR[](含义同上);
如何更新答案呢?
对于 u->v 这条边, 如果 preR[u] ≠ pre[v], 那么 ans=min{ ans,disR[u] + wu->v+ dis[v] };
都跑完后, 输出 ans;
AC 代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<queue>
- using namespace std;
- #define ll long long
- #define INFll 0x3f3f3f3f3f3f3f3f
- #define mem(a,b) memset(a,b,sizeof(a))
- const int maxn=1e5+50;
- int n,m,k;
- ll ans;
- int tourist[maxn];
- int num;
- int head[maxn];
- struct Edge
- {
- int to;
- ll w;
- int next;
- }G[maxn*10];
- void addEdge(int u,int v,ll w)
- {
- G[num]={v,w,head[u]};
- head[u]=num++;
- }
- struct Dij
- {
- struct Heap
- {
- int u;
- ll w;
- bool operator <(const Heap& obj) const
- {
- return w> obj.w;
- }
- };
- ll dis[maxn];
- int pre[maxn];
- bool vis[maxn];
- priority_queue<Heap>q;
- void dij()// 第一遍 dij 求解出 pre[],dis[]
- {
- mem(vis,false);
- while(!q.empty())
- q.pop();
- for(int i=0;i <maxn;++i)
- dis[i]=INFll;
- for(int i=1;i <= k;++i)
- {
- int u=tourist[i];
- dis[u]=0;
- pre[u]=u;
- q.push({u,0});
- }
- while(!q.empty())
- {
- Heap tmp=q.top();
- q.pop();
- int u=tmp.u;
- if(vis[u])
- continue;
- vis[u]=true;
- for(int i=head[u];~i;i=G[i].next)
- {
- int v=G[i].to;
- ll w=G[i].w;
- if(i&1)
- continue;
- if(dis[v]> dis[u]+w)
- {
- dis[v]=dis[u]+w;
- pre[v]=pre[u];
- q.push({v,dis[v]});
- }
- }
- }
- }
- ll disR[maxn];
- int preR[maxn];
- void dijR()// 第二遍 dij 求出 disR[],preR[],ans
- {
- mem(vis,false);
- while(!q.empty())
- q.pop();
- for(int i=0;i <maxn;++i)
- disR[i]=INFll;
- for(int i=1;i <= k;++i)
- {
- int u=tourist[i];
- disR[u]=0;
- preR[u]=u;
- q.push({u,0});
- }
- while(!q.empty())
- {
- Heap tmp=q.top();
- q.pop();
- int u=tmp.u;
- if(vis[u])
- continue;
- vis[u]=true;
- /**
- 错误的更新 ans 判断;
- 假设最终答案是 x->y 的最短路;
- 如果只是判断节点 u 的 preR 和 pre 是否相等;
- 假设 pre[u]=x;
- 那么, 如果 w[x][u] = w[y][u];
- 根据更新条件, 此处 w 相等, 不更新;
- 所以 preR[u]=w;
- 来到当前 if 的时候, preR[u]=pre[u]=x;
- 但是令 preR[u]=y 也可以;
- 所以, 在这种情况下, 本来该更新 ans 的并没有更新
- */
- // if(preR[u] != pre[u])
- // ans=min(ans,dis[u]+disR[u]);
- for(int i=head[u];~i;i=G[i].next)
- {
- int v=G[i].to;
- ll w=G[i].w;
- if(!(i&1))
- continue;
- if(preR[u] != pre[v])// 如果更新 u,v 的不是 K 中的同一个点, 更新 ans
- ans=min(ans,disR[u]+w+dis[v]);
- if(disR[v]> disR[u]+w)
- {
- disR[v]=disR[u]+w;
- preR[v]=preR[u];
- q.push({v,disR[v]});
- }
- }
- }
- }
- }_dij;
- ll Solve()
- {
- ans=INFll;
- _dij.dij();
- _dij.dijR();
- return ans;
- }
- void Init()
- {
- num=0;
- mem(head,-1);
- }
- int main()
- {
- // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
- int test;
- while(~scanf("%d",&test))
- {
- while(test--)
- {
- Init();
- scanf("%d%d%d",&n,&m,&k);
- for(int i=1;i <= m;++i)
- {
- int u,v,w;
- scanf("%d%d%d",&u,&v,&w);
- addEdge(u,v,w);//num 为偶数, 正向边
- addEdge(v,u,w);//num 为奇数, 反向边
- }
- for(int i=1;i <= k;++i)
- scanf("%d",tourist+i);
- printf("%lld\n",Solve());
- }
- }
- return 0;
- }
- View Code
洛谷 P5304 [GXOI/GZOI2019]旅行者(最短路)
来源: http://www.bubuko.com/infodetail-3034370.html