Final Dash
分层图！
题目
传送门：青蛙跳
考察知识点：分层图，拆点，最短路
分层图
概念
分层图，顾名思义就是分很多层的图，也就是类似二维数组，不再是一个单一的平面，而是一个立体化的东西不只有长宽，也有了自己的厚度即为层数
范围
一些图论题，比如最短路、网络流等，题目对边的权值提供可选的操作，比如可以将一定数量的边权减半，在此基础上求解最优解。
建立多层相同或相似的图, 并在图与图之间进行连边，可以实现两种性质的图之间的转移,或是图与图之间有限制的转移。
算法思路
根据是否进行题目提供的操作以及操作次数的不同，会产生非常多的情况，如果考虑何时使用操作，情况更是多。
如果将在图上求解最短路看成是在二维平面上进行的，引入进行操作的次数k做为第三维，那么这个三维空间就理应可以包含所有的情况，便可以在这个三维空间上解决问题。每进行一次操作k+1，除了操作的边，其他边没有任何变化，在k=0,1,2,…时，图都是一样的，那么就将图复制成k+1份，第i层图代表进行了i次操作后的图。每相邻两层图之间的联系，应该决定了一次操作是发生在哪条边上（何时进行操作）。根据操作的特点（对边权的修改）可以i层点到i+1层点的边来表示一次操作。
核心
for(int i=1; i<=m; i++){
int x,y,z; cin>>x>>y>>z;
add(x,y,z); add(y,x,z);
for(int j=1; j<=k; j++){
add(j*n+x,j*n+y,z); add(j*n+y,j*n+x,z);
add((j-1)*n+x,j*n+y,0); add((j-1)*n+y,j*n+x);
}
}
|
分析
题目中提及“所有荷叶的状态1秒会发生一次交换”，规模不变，整个图呈现另外一种状态，这其实是一个分层图的模型，本题相对简单，就是两层。所谓的分层图，就是每个点有几种可能的状态，就拆成几个不同的点，每个点代表一个状态。
对于此题来说，每个点只有红绿两色，于是我们可以把每个点拆成两个点。分别是奇数秒和偶数秒的状态。
拆完点之后，最重要的事情就是建边！
首先，停留或者走一条边都是花费1时刻，因此每次操作以后点的状态都发生了改变。对于停留，其实我们可以把拆出来的两个点互相连边，然后绿点去红点连权值为s[i]的边，红去绿边权为0。
其次，对于原本的路径，实际上就是如果当前点是绿点，那么就连一条边去目的地的相反状态(该状态与初始状态有关)，边权按题意来算。（红点同理）。
简图
/*样例*/
4 5
1 0 1 0
10 10 100 10
5 20 15 10
1 2 30
2 3 40
1 3 20
1 4 200
3 4 200
|
代码
#define ll long long
using namespace std;
const int N=100005;
int n,m,cnt;
int q[N];ll d[N];
bool mp[N],inq[N];
int w[N],s[N];
int h[N],head[N];
struct data{
int to,next,v;
}ed[N],e[N];
void ins(int u,int v,int w){
ed[++cnt].to=v;
ed[cnt].v=w;
ed[cnt].next=h[u];
h[u]=cnt;
}
void insert(int u,int v,int w){
e[++cnt].to=v;
e[cnt].v=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void build(int x)
{
insert(x,x+n,s[x]); insert(x+n,x,0);
for(int i=h[x];i;i=ed[i].next){
int de=abs(w[x]-w[ed[i].to]);
if(mp[x]!=mp[ed[i].to]){
insert(x,ed[i].to,ed[i].v+de);
insert(x+n,ed[i].to+n,max(0,ed[i].v-de));
}
else{
insert(x,ed[i].to+n,ed[i].v);
insert(x+n,ed[i].to,ed[i].v);
}
}
}
void spfa()
{
int t=0,w=1;
memset(d,127,sizeof(d));
if(mp[1]){q[0]=1;d[1]=0;inq[1]=1;}
else{q[0]=n+1;d[n+1]=0;inq[n+1]=1;}
while(t!=w){
int now=q[t];t++;if(t==10001)t=0;
for(int i=head[now];i;i=e[i].next){
if(e[i].v+d[now]<d[e[i].to]){
d[e[i].to]=d[now]+e[i].v;
if(!inq[e[i].to]){
inq[e[i].to]=1;
q[w++]=e[i].to;
if(w==10001)w=0;
}
}
}
inq[now]=0;
}
cout<<min(d[n],d[n+n]);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>mp[i];
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=m;i++)
{
int x,y,z; cin>>x>>y>>z;
ins(x,y,z);
}
cnt=0;
for(int i=1;i<=n;i++) build(i);
spfa();
return 0;
}
|
