BalticOI2017 Toll

2022/6/4 23:22:53

编程Tag： 矩阵 int ... ch DP quad Toll BalticOI2017

本文主要是介绍BalticOI2017 Toll，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前置芝士1 分层图

分层图，顾名思义，就是有好多层的图，可以想象成一个个平面

分层图板子题 Revamping Trails G

前置芝士2 动态dp

传送门动态DP基础 - GKxx 的博客 - 洛谷博客 (luogu.com.cn) 本地也有！

一句话：把矩阵乘法定义新运算

回到这题

知道了这两道题后，这就是个板子题了，首先因为题目说 $\lfloor\frac{b}{k}\rfloor=1+\lfloor{\frac{a}{k}\rfloor}$ ，所以相邻的 k 个点不会连边（这里的相邻指$ 1\to k,2\to2k,3\to3k$)，所以把这张图分成$\lfloor\frac{n-1}{k}\rfloor$层，每层只会向下一层连边，是一个DAG，每个结点的度数不会超过 k。

考虑dp，设$f_u$是从 u 到 b 的最短路，转移就是$f_u=\min\{f_v+t_{u,v}\}$

把除以 k 下取整相同的所有 f（即每一层的 f ）按照模 k 的大小一次放到$1*k$的矩阵里，那么转移可以写成

$[f_a\quad f_b \quad ...]\times $$ \begin{bmatrix} t_{a,x} & t_{a,y} & ... \ t_{b,x} & t_{b,y} & ... \ ... & ... & ... \end{bmatrix} $$=[f_x\quad f_y\quad ...]$

注意这里的矩阵乘法就是动态dp的定义新运算了！

$(AB)_{i,j}=min^{k-1}_{x=0}\{A_{i,x}+B_{x,j}\}$，因为加法对最值运算有分配律，所以这样的矩阵乘法也有结合律，所以用线段树维护区间乘积，每次查询直接乘。

点击查看代码

//CAN'T FORGET
//CAN'T FORGET
//CAN'T FORGET

//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define _ 0
const int maxn=2e6+5;
const int inf=1e9+7;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int k,n,m,q;
struct Matrix{
	int m[5][5];
	Matrix operator *(Matrix o)const{
		Matrix res;
		for(int i=0;i<=k-1;i++)
		{
			for(int j=0;j<=k-1;j++)
			{
				res.m[i][j]=inf;
				for(int K=0;K<k;K++)
					res.m[i][j]=min(res.m[i][j],m[i][K]+o.m[K][j]);
			}
		}
		return res;
	}
}tr[maxn],ans;
void update(int rt,int l,int r,int x,int a,int b,int nm)
{
	if(l==r)
	{
		tr[rt].m[a][b]=nm;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		update(rt<<1,l,mid,x,a,b,nm);
	else
		update(rt<<1|1,mid+1,r,x,a,b,nm);
	tr[rt]=tr[rt<<1]*tr[rt<<1|1];
}
void query(int rt,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
	{
		ans=ans*tr[rt];
		return ;
	}
	int mid=(l+r)>>1;
	if(L<=mid)
		query(rt<<1,l,mid,L,R);
	if(R>mid)
		query(rt<<1|1,mid+1,r,L,R);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//	freopen("toll.in","r",stdin);
//	freopen("toll.out","w",stdout);
    cin>>k>>n>>m>>q;
	int num=(n-1)/k;
	for(int i=1;i<=(num<<2);i++)
		for(int j=0;j<=k-1;j++)
			for(int K=0;K<=k-1;K++)
				tr[i].m[j][K]=inf;
	for(int i=1;i<=m;i++)
	{
		int a,b,t;
		cin>>a>>b>>t;
		update(1,0,num,a/k,a%k,b%k,t);
	}
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(a/k>=b/k)
		{
			cout<<"-1\n";
			continue;
		}
		for(int i=0;i<=k-1;i++)
		{
			for(int j=0;j<=k-1;j++)
			{
				if(i==j)
					ans.m[i][j]=0;
				else
					ans.m[i][j]=inf;
			}
		}
		query(1,0,num,a/k,b/k-1);
		if(ans.m[a%k][b%k]==inf)
			cout<<"-1\n";
		else
			cout<<ans.m[a%k][b%k]<<"\n";
	}
	return ~~(0^_^0);
}
/*
Notes:
1.看所有题目
2.注意数据范围
3.想想自己还能做什么而不是做了什么
4.看清题目!!!
5.记得把调试代码删掉!!!!
6.longlong时 1要写成1ll
7.Think twice code once, think once code forever!
*/

这篇关于BalticOI2017 Toll的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

BalticOI2017 Toll

前置芝士1 分层图

前置芝士2 动态dp

回到这题

相关编程文章