中国队勇夺世界杯_1970年世界杯 - hcsjlp.com

简介

是一种思想。如果题目需要对图进行固定方式的修改，而且修改次数有限或者说有循环，那么就可以使用分层图。

具体而言，将图建立成若干层，每层之内正常连边，层与层之间的连边依据题意中修改的前提条件。

当然上面是最裸的分层图。

还有些分层图可用于表示不同的状态，以不同状态在图上移动时，信息可能有所变化， 层与层之间的连边依据题意中状态转移的条件。

分层一般情况下用 \(j*n+u\) 的形式分层，表示这是第 \(j\) 层的 \(u\) 节点。

例题

冻结

发现 k 小的离谱，考虑直接建 k+1 层图，然后直接跑最短路。

层内正常连边，层与层之间 \(j*n+u\) 向 \((j+1)*n+v\) 连边权为 \(w/2\) 的边即可。

code：

#include

#include

#include

using namespace std;

const int N=100;

const int M=1e3+10;

const int inf=2e9;

int n,m,k;

int res=inf;

struct Edge{

int v,w;

};

struct node{

int d;

long long dis;

bool operator < (const node a) const{

return a.dis

}

};

vector vec[50*N];

void add(int u,int v,int w){

vec[u].push_back({v,w});

return ;

}

int dis[N*50];

bool vis[N*50];

priority_queue que;

void dij(){

for(int i=1;i<=n*k+n;i++) dis[i]=inf;

dis[1]=0;

que.push({1,0});

while(!que.empty()){

node u=que.top();que.pop();

if(vis[u.d]) continue;

vis[u.d]=1;

// cout<

for(auto nxt: vec[u.d]){

dis[nxt.v]=min(dis[nxt.v],dis[u.d]+nxt.w);

que.push({nxt.v,dis[nxt.v]});

}

}

return ;

}

int main(){

cin>>n>>m>>k;

for(int i=1;i<=m;i++){

int u,v,w;

cin>>u>>v>>w;

for(int j=0;j<=k;j++) add(j*n+u,j*n+v,w),add(j*n+v,j*n+u,w);

for(int j=0;j

}

dij();

for(int i=0;i<=k;i++){

res=min(res,dis[i*n+n]);

}

cout<

return 0;

}

移动迷宫

直接粘我在洛谷上写的题解

观察到 \(n,m\le 1e5\) 那么就可以知道一个做法是超时的：

每走一步就去更新一遍边权。

所以我们要对这个式子 \(\frac{1}{1-t} \pmod {754974721}\) 找规律。

重复代入三次后发现得出的数为 \(t\) 。

这时候想到了记录一个 \(step\) 表示当前走的是第几步，然后用 \(step \bmod 3\) 这类操作去计算边权。

仔细思考一下似乎并不好写而且正确性并没有多么大，简单来说就是没有前途。

那么接着就想到了分层图。

将三种边权分到三层建图，具体地说：

我们令图分为 \(1,2,3\) 层，每条边的边权在循环中的值为 \(w_1,w_2,w_3\) 。

那么对于一条 \(u\) 到 \(v\) 的边，我们从第一层的 \(u\) 向第二层的 \(v\) 建一条 \(w_1\) 的边，第二层的 \(u\) 向第三层的 \(v\) 建一条 \(w_2\) 的边，第三层的 \(u\) 向第一层的 \(v\) 建一条 \(w_3\) 的边。

反之亦然。

直接在建好的分层图上跑最短路即可。

AC code：

实现的并不优美，致歉。

#include

#include

#include

#include

#include

#define int long long

#define ll __int128

using namespace std;

const int N=1e5+50;

const int M=1e5+50;

const int p=754974721;

int n,m;

struct node{

int v,w;

};

vector vec[3*N];

bool vis[3*N];

ll dis[3*N];

queue que;

int gn(int i,int k){

return i+k*n;

}

ll exgcd(ll a,ll b,ll &x,ll &y){

if(b==0){

x=1;

y=0;

return a;

}

int res=exgcd(b,a%b,x,y);

int tmp=x;

x=y;

y=tmp-a/b*y;

return res;

}

ll qpow(ll a,ll b,ll p){

ll res=1;

while(b){

if(b&1) res=res%p*a%p;

a=a%p*a%p;

b>>=1;

}

return res%p;

}

ll modify(ll k){

// ll x,y;

// exgcd(1-k,p,x,y);

return qpow((1-k+p)%p,p-2,p);

}

void add(int u,int v,int w){

vec[u].push_back({v,w});

return ;

}

int spfa(int u){

for(int i=1;i<=3*n;i++) dis[i]=1e18;

dis[u]=0;

vis[u]=1;

que.push(u);

while(!que.empty()){

int x=que.front();que.pop();

vis[x]=0;

for(int j=0;j<(int)vec[x].size();j++){

int y=vec[x][j].v;

int w=vec[x][j].w;

if(dis[y]>dis[x]+w){

dis[y]=dis[x]+w;

if(!vis[y]){

que.push(y);

vis[y]=1;

}

}

}

}

return min(dis[gn(n,0)],min(dis[gn(n,1)],dis[gn(n,2)]));

// return dis[gn(n,0)];

}

signed main(){

cin>>n>>m;

for(int i=1;i<=m;i++){

int u,v,w;

cin>>u>>v>>w;

int w2=modify(w);

w2=(w2%p+p)%p;

int w3=modify(w2);

w3=(w3%p+p)%p;

add(gn(u,0),gn(v,1),w);

add(gn(u,1),gn(v,2),w2);

add(gn(u,2),gn(v,0),w3);

add(gn(v,0),gn(u,1),w);

add(gn(v,1),gn(u,2),w2);

add(gn(v,2),gn(u,0),w3);

}

int ans1=spfa(gn(1,0));

cout<

return 0;

}

最优贸易

这就是上述说的以不同状态分层。

将图分为三层，第一层表示什么都没干，第二层表示我买了东西，第三层表示我卖出东西。

第一层中 \(u\) 向第二层中 \(u\) 转移时，相当于在 \(u\) 城市买入水晶球，所以建立边权为 -w 的边。

第二层中 \(u\) 向第三层中 \(u\) 转移时，相当于在 \(u\) 城市卖出水晶球，所以建立边权为 w 的边。

因为我们在不同城市游走是没有代价的，所以每层之内建边的边权为 0 。

然后用 SPFA 解最长路即可。

code：

#include

#include

#include

#include

#include

#include

using namespace std;

const int N=1e5+50;

const int M=5e5+50;

int n,m;

struct node{

int v,w;

};

int ge(int i,int k){

return i+k*n;

}

bool vis[3*N];

vector G[3*N];

queue que;

int dis[3*N];

void add(int u,int v){

G[ge(u,0)].push_back({ge(v,0),0});

G[ge(u,1)].push_back({ge(v,1),0});

G[ge(u,2)].push_back({ge(v,2),0});

return ;

}

void spfa(int u){

for(int i=1;i<=3*n;i++) dis[i]=-1e9;

dis[u]=0;

vis[u]=1;

que.push(u);

while(!que.empty()){

int x=que.front();que.pop();

vis[x]=0;

for(int j=0;j<(int)G[x].size();j++){

int y=G[x][j].v;

int w=G[x][j].w;

if(dis[y]

dis[y]=dis[x]+w;

if(!vis[y]){

que.push(y);

vis[y]=1;

}

}

}

}

}

int main(){

cin>>n>>m;

for(int i=1;i<=n;i++){

int w;

cin>>w;

G[ge(i,0)].push_back({ge(i,1),-w});

G[ge(i,1)].push_back({ge(i,2),w});

}

for(int i=1;i<=m;i++){

int u,v,op;

cin>>u>>v>>op;

add(u,v);

if(op==2){

add(v,u);

}

}

spfa(ge(1,0));

cout<

return 0;

}