YLCHUP头像
【最短路性质+计数hash】题解:矿井寻踪(trace)_图论_动态规划_拓扑排序_哈希优化_C++算法竞赛封面图

【最短路性质+计数hash】题解:矿井寻踪(trace)_图论_动态规划_拓扑排序_哈希优化_C++算法竞赛

B.矿井寻踪(trace)

题目描述

丰富的美食让你们心满意足,肚子饱饱的你准备下井探矿,寻找星露谷失落的珍宝。

每个矿井间通过错综复杂的隧道连接,而且还受到结界的影响。具体而言,矿井和隧道呈现为一张有向带权图,其中权值是通过该隧道的时间。由于里面时常有怪物出没,经过前人的探索,每条隧道被设立了魔法结界,为了保障安全都只有一个方向是可以通过,即这是一张有向图。

不过森林的魔法波动让隧道结界发生了变化。第 000 天,隧道没有变化,而在第 1∼m1 \sim m1∼m 天的凌晨,若第 iii 天的波动值 pip_ipi​ 为 111,则第 iii 条隧道的结界方向会发生变化,直至午夜时恢复原结界方向,即这条边会反向,一天后恢复。若 pip_ipi​ 为 000 则表示该隧道结界足够强大,未受到波动影响。

假设起点在矿井 S=1S=1S=1 号矿井,珍宝的位置在矿井 T=2T=2T=2 号矿井,你想知道如果你中午进入起点,从 SSS 到达 TTT 的最短时间相比于魔法波动前(即相比于第 000 天),会变大、变小还是不变?保证第 000 天两者连通。

输入格式

第一行输入两个数 n,mn,mn,m,表示矿井和隧道的数量;

接下来输入一行一个长度为 mmm 的字符串 ppp,其中 pip_ipi​ 表示第 iii 天隧道 iii 是否受到波动影响。

最后 mmm 行每行输入三个数 ui,vi,wi (1≤ui,vi≤n, 1≤wi≤105)u_i,v_i,w_i\ (1 \le u_i,v_i \le n,\ 1 \le w_i \le 10^5)ui​,vi​,wi​ (1≤ui​,vi​≤n, 1≤wi​≤105),表示这条隧道的起点、终点和通过时间。

输出格式

第一行先输出第 000 天从起点到珍宝的最短时间。

接下来 2∼m+12 \sim m+12∼m+1 行:

  • 若今天从起点到珍宝的最短时间变小了,输出 HAPPY;
  • 若今天从起点到珍宝的最短时间变大了,输出 SAD;
  • 若今天从起点到珍宝的最短时间未变,输出 SOSO。

样例1输入

4 5
11111
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12

样例1输出

18
SAD
SAD
SAD
SOSO
HAPPY

样例2输入

7 5
11111
1 3 2
1 6 3
4 2 4
6 2 5
7 5 6

样例2输出

8
SOSO
SAD
SOSO
SAD
SOSO

样例3输入

10 14
11111111111111
1 7 9
1 8 3
2 8 4
2 6 11
3 7 8
3 4 4
3 2 1
3 2 7
4 8 4
5 6 11
5 8 12
6 10 6
7 10 8
8 3 6

样例3输出

10
SOSO
SAD
HAPPY
SOSO
SOSO
SOSO
SAD
SOSO
SOSO
SOSO
SOSO
SOSO
SOSO
SAD

对于所有数据,保证 2≤n≤105, 1≤m≤105, 1≤ui,vi≤n, 1≤wi≤105, pi∈{0,1}2 \le n \le 10^5,\ 1 \le m \le 10^5,\ 1 \le u_i,v_i \le n,\ 1 \le w_i \le 10^5,\ p_i \in \{0,1\}2≤n≤105, 1≤m≤105, 1≤ui​,vi​≤n, 1≤wi​≤105, pi​∈{0,1}。保证第 000 天 S,TS,TS,T 连通,保证没有重边和自环。

题解

提供一种最短路图上dp计数的方法,直接边跑边做就好了,没必要单独存出来一个图再拓扑。

对于乘法会炸提供一种双模数hash的解决方法。

题目要O(1)求将有向图中每条边反向后,从S->T的最短路长度变化情况。
显然如果新加入的边会有用,当且仅当加入后新图S->T中所有最短路都必须经过新边。

具体地,设原用时为dis(1,2),若反转边(u,v,w)则新用时为dis(1,v)+w+dis(u,2)
然后分讨大小关系:
原用时<新用时 -- HAPPY
原用时=新用时 -- SOSO
原用时>新用时:
  发现当且仅当所有的原最短路径都经过这条边时,耗时更久
  意思是它在当前所有最短路的“主干道”上,它一旦反向就会让原来所有的最短路“跑不通”,肯定会更劣
  考虑如何判断,注意到如果把只在最短路上的边拿出来形成的“最短路图”是一个DAG,所以可以正反跑拓扑记录到每个点的最短路条数
  则经过一条边(u,v)的最短路条数为cntS[u]*cntT[v],判断它是否等于原来总的最短路条数即可判断这种情况
  但是总的最短路条数只要构造一个边权都相等的菱形图就可以卡到2^n次方级别,为了避免乘法溢出可以用双模数hash,出错概率比较低
  (如果满足条件hash一定是对的,会出错当且仅当P1*P2能整除cntS[u]*cntT[v],但概率很小) 
  
注:最好的方法是把最短路图看成无向,然后Tarjan求割边,一条边在“主干道”上等价于它是最短路图上的割边 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7,P1=998244353,P2=1e9+7;

int n,m; string p;
struct Node{
	ll d; int u;
	bool operator<(Node p)const{
		return d>p.d;
	}
};

ll c1[3][N],c2[3][N];

void dij(int s,vector<array<ll,2>> (&G)[N],vector<ll> &dis){
	for(int i=0;i<=n;i++) dis[i]=1e18;
	vector<int> vis(n+1);
	priority_queue<Node> Q; Q.push({0,s}); dis[s]=0;
	c1[s][s]=c2[s][s]=1;
	while(!Q.empty()){
		int u=Q.top().u; Q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto it:G[u]){
			int v=it[0]; ll w=it[1];
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w; Q.push({dis[v],v});
				c1[s][v]=c1[s][u],c2[s][v]=c2[s][u];
			}else if(dis[v]==dis[u]+w){
				c1[s][v]=(c1[s][v]+c1[s][u])%P1,c2[s][v]=(c2[s][v]+c2[s][u])%P2;
			}
		}
	}
}

vector<array<ll,2>> G[N],rG[N]; //正图、反图 
int u[N],v[N],w[N];

void solve()
{
	cin>>n>>m>>p;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
		G[u[i]].push_back({v[i],w[i]}); rG[v[i]].push_back({u[i],w[i]});
	}
	vector<ll> ds(n+1,1e18),dt(n+1,1e18);
	dij(1,G,ds); dij(2,rG,dt);
	cout<<ds[2]<<'\n';
	for(int i=1;i<=m;i++){
		if(p[i-1]=='0'){
			cout<<"SOSO\n"; continue;
		}
		ll tim=ds[v[i]]+w[i]+dt[u[i]]; //新用时
		if(tim<ds[2]) cout<<"HAPPY\n";
		else if(tim==ds[2]) cout<<"SOSO\n";
		else{
			//在原来的最短路上且方案数相等,所以是必经之路
			if(ds[u[i]]+w[i]+dt[v[i]]==ds[2] &&
			   c1[1][u[i]]*c1[2][v[i]]%P1==c1[1][2]%P1 &&
			   c2[1][u[i]]*c2[2][v[i]]%P2==c2[1][2]%P2){  
				cout<<"SAD\n";
			}else{
				cout<<"SOSO\n";
			}
		} 
	}
}

signed main()
{
	freopen("trace.in","r",stdin);
	freopen("trace.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/YLCHUP/article/details/170743460

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--