此题我要讲一种异或优化建图
-
题意:某国有N座城市,编号从1到N。 (N<=1e5 , M<=5e5)
该国的交通工具主要有飞机和高铁两种对于任意的两座城市 i 和 j ,人们可以花费( i xor j ) * C 块钱从城市 i 坐飞机到城市 j ,这里 C 为该国规定的费用常数。该国有 M 条单向的高铁线路,第 i 条高铁从第 Xi 号城市开往第 Yi 个城市,乘坐这条高铁需要花费 Vi 的块钱。问从城市 A 前往城市 B 最少需要多少费用? -
此题如果暴力建边的话时间或空间复杂度都是(n^2+m)肯定不行
所以我考虑异或(位运算)的性质:按位分离计算?
因此我们把十进制脑补成二进制,加一个维度:位!!!
对于i,j的二进制第s位异或成1才能加上边权(1<<s) * C
所以对于点i可以连出一条到点i^(1<<s) [0<=s<=20]的边权位(1<<s) * C 的边
举个栗子:点 2->7
3=(010),7=(111)
3(010)->4(011),sumw+=(1<<0)C
4(011)->7(111),sumw+=(1<<2)C
检验 sumw = [ (1<<0)+(1<<2) ] * C = (101) * C = 5 * C = ( 3^7 ) * C
因此建边如下:
for(int i=1;i<=m;i++) {
int u,v;ll w;
scanf("%d%d%lld",&u,&v,&w);
add_edge(u,v,w);
}
for(int i=0;i<=n;i++) {
for(int j=0;j<=20;j++) {
int v=i^(1<<j);
if(v<=n) {
add_edge(i,v,(1<<j)*c);
}
}
}
所整体从起点A跑一遍Dijkstra就可以了
(图论的核心是如何建边)会了上面的建边代码很简单:
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int M=1e7+5;
int nxt[M],to[M],head[N],tot;
ll len[M],dis[N];
void add_edge(int u,int v,ll w) {
tot++; nxt[tot]=head[u]; len[tot]=w; to[tot]=v; head[u]=tot;
}
struct node {
int p;ll w;
bool operator<(const node &u) const{return w>u.w;}
};
priority_queue<node> Q;
bool mark[N];
void DJ(int s) {
Q.push((node){s,0});
dis[s]=0;
while(!Q.empty()) {
int u=Q.top().p; Q.pop();
if(mark[u]) continue;
mark[u]=true;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
if(!mark[v]&&dis[v]>dis[u]+len[i]) {
dis[v]=dis[u]+len[i];
Q.push((node){v,dis[v]});
}
}
}
}
int main() {
int n,m,c,X,Y;
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=m;i++) {
int u,v;ll w;
scanf("%d%d%lld",&u,&v,&w);
add_edge(u,v,w);
}
for(int i=0;i<=n;i++) {
for(int j=0;j<=20;j++) {
int v=i^(1<<j);
if(v<=n) {
add_edge(i,v,(1<<j)*c);
// printf("%d %d %lld\n",i,v,(1<<j)*c);
}
}
}
scanf("%d%d",&X,&Y);
memset(dis,0x3f,sizeof(dis));
DJ(X);
printf("%lld",dis[Y]);
return 0;
}