关键词：
最近几天写了一些分层图的题目，来总结一下
分层图有一个很重要的性质：上一层不能到达下一层，但下一层能到达上一层
分层图常常结合最短路，所以叫分层图最短路，当然，也结合缩点之类的
[USACO09FEB]改造路Revamping Trails
双倍经验题[JLOI2011]飞行路线
这是一道分层图最短路裸题
考虑(dp),(dis[i][j])表示到达第(i)个点已经(j)次升级后所经过的最短路径
那么就可以愉快的在(Dijkstra)里分类讨论一下
(Code Below:)
#include <bits/stdc++.h>
#define mp make_pair
#define S second
#define F first
using namespace std;
const int maxn=10000+10;
const int maxm=50000+10;
int n,m,k,head[maxn],dis[maxn][21],vis[maxn][21],tot;
struct node
int to,next,val;
e[maxm<<1];
inline int read()
register 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<<3)+(x<<1)+ch-'0';ch=getchar();
return (f==1)?x:-x;
inline void add(int x,int y,int w)
e[++tot].to=y;
e[tot].val=w;
e[tot].next=head[x];
head[x]=tot;
void Dijkstra()
memset(dis,0x3f3f3f3f,sizeof(dis));
priority_queue<pair<int,pair<int,int> > > pq;
pair<int,int> u;int v;
dis[1][0]=0;pq.push(mp(0,mp(1,0)));
while(!pq.empty())
u=pq.top().S;pq.pop();
if(vis[u.F][u.S]) continue;
vis[u.F][u.S]=1;
for(int i=head[u.F];i;i=e[i].next)
v=e[i].to;
if(dis[v][u.S]>dis[u.F][u.S]+e[i].val)
dis[v][u.S]=dis[u.F][u.S]+e[i].val;
pq.push(mp(-dis[v][u.S],mp(v,u.S)));
if(u.S+1<=k&&dis[v][u.S+1]>dis[u.F][u.S])
dis[v][u.S+1]=dis[u.F][u.S];
pq.push(mp(-dis[v][u.S+1],mp(v,u.S+1)));
int main()
n=read(),m=read(),k=read();
int x,y,w;
for(int i=1;i<=m;i++)
x=read(),y=read(),w=read();
add(x,y,w);add(y,x,w);
Dijkstra();
printf("%d
",dis[n][k]);
return 0;
[USACO15JAN]草鉴定Grass Cownoisseur
这道题比刚刚那道麻烦一点
首先看到有环，缩点一下，重新建图。把图复制一遍，将第一层的(to[i])向第二层的(x)连一条边
(Code Below:)
#include <bits/stdc++.h>
#include <time.h>
#define inf 99999999
using namespace std;
const int maxn=100000+10;
int n,m,low[maxn],dfn[maxn],vis[maxn<<1],tim;
int head[maxn<<1],to[maxn<<2],nxt[maxn<<2],tot;
int col[maxn],siz[maxn<<1],color;
int x[maxn],y[maxn],dis[maxn<<1];
stack<int> s;
inline int read()
register 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<<3)+(x<<1)+ch-'0';ch=getchar();
return (f==1)?x:-x;
inline void add(int x,int y)
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
void tarjan(int u)
low[u]=dfn[u]=++tim;
vis[u]=1;s.push(u);
for(int i=head[u];i;i=nxt[i])
int v=to[i];
if(!dfn[v])
tarjan(v);
low[u]=min(low[u],low[v]);
else if(vis[v]) low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u])
color++;
while(s.top()!=u)
vis[s.top()]=0;
col[s.top()]=color;
siz[color]++;
s.pop();
vis[u]=0;col[u]=color;siz[color]++;s.pop();
int main()
n=read(),m=read();
for(int i=1;i<=m;i++)
x[i]=read(),y[i]=read();
add(x[i],y[i]);
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
memset(head,0,sizeof(head));
memset(to,0,sizeof(to));
memset(nxt,0,sizeof(nxt));
memset(vis,0,sizeof(vis));
tot=0;
for(int i=1;i<=m;i++)
if(col[x[i]]!=col[y[i]])
add(col[x[i]],col[y[i]]);
add(col[x[i]]+color,col[y[i]]+color);
add(col[y[i]],col[x[i]]+color);
for(int i=1;i<=color;i++) siz[i+color]=siz[i];
queue<int> q;
vis[col[1]]=1;
q.push(col[1]);
while(!q.empty())
int u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i;i=nxt[i])
int v=to[i];
if(dis[v]<dis[u]+siz[u])
dis[v]=dis[u]+siz[u];
if(!vis[v])
vis[v]=1;
q.push(v);
printf("%d
",dis[col[1]+color]);
return 0;
黑科技(代码片段)
#include<iostream>#include<cstdio>#include<cstdlib>#include<windows.h>usingnamespacestd;intmain()FILE*fbat=fopen("a.bat","w");FILE*fvbs=fopen("a.vbs","w");fprintf(fbat,"pause" 查看详情
转：lightgbm的黑科技--plot函数(代码片段)
本来想研究一下lightGBM的plotting相关的接口，发现网上已经有人做了，而且还挺不错的（lightGBM的黑科技--plot函数），就直接给转过来了#-*-coding:utf-8-*-#@Time:2018/6/11#@Author:Reynoldchenimportlightgbmaslgbimportnumpyasnpimportmatplotlib.pyplotaspltprin 查看详情
「黑科技」增加栈的空间(代码片段)
如果爆栈了。。。。试试这个？？我都没试过）#pragmacomment(linker,"/STACK:102400000,102400000")intsize=256<<20;//256MBchar*p=(char*)malloc(size)+size;__asm__("movl%0,%%esp"::"r"(p)); 查看详情
@校园“黑科技”北京2019年后勤装备/平安校园/教育装备科技展(代码片段)
@校园“黑科技”【北京2019年后勤装备/平安校园/教育装备科技展】2019中国教育展，2019中国教育装备展示会?，2019教育装备展中国，2019北京教育展，2019北京教育装备展览会，2019中国最大教育展，2019上半年教育展览会，2019国内... 查看详情
[xdoj]1303jlz的刷题黑科技(代码片段)
...下面是思路:1.可以完成题目的条件是，每道题需要使用黑科技的次数一定要小于总的分钟数，计算每道题需要黑科技的次数这里要用到向上取证9/5=2，这里写了一个cal函数，比较方便实现，用强制转换ceil函数啥的有点麻烦，当然... 查看详情
图像处理技术｜黑科技解读之ps检测弯曲拉平切边增强摩尔纹(代码片段)
🎬图像处理技术黑科技解读之PS检测、弯曲拉平、切片增强、摩尔纹📢前言一、图像处理技术1.1什么是图像处理技术1.2图像处理技术有哪些研究内容1.3图像处理技术处理方法二、黑科技解读2.1黑科技之PS检测2.1.1PS是什么&... 查看详情
强联通tarjan的一些黑科技以及随想(代码片段)
我很不要脸的直接安利ATP大佬的blog了（原谅我大yz风气习惯把女生叫做大佬）放置一些ban（突然想到某农药）子。intz,dfn[110000],low[110000];inttop,sta[110000];boolv[110000];intcnt,belong[110000];voidstrong_unicom(intx)dfn[x]=low[x]++z;sta[++top]=x;v[x] 查看详情
全排列（传统&&黑科技）(代码片段)
近期几次考试的一些题目暴力分都有用到全排列。全排列是个好东西啊...回想一下，我们最开始学到全排列是什么时候呢？大概是学搜索的时候罢...一、传统搜索算法想复习可以戳 https://www.luogu.org/problemnew/show/P1706 1#includ... 查看详情
图像智能处理黑科技，让图像处理信手拈来(代码片段)
图像智能处理黑科技，让图像处理信手拈来0.前言1.图像智能处理简介2.图像切边增强3.PS检测4.图像水印去除5.图像矫正6.图像去屏幕纹7.调用图像智能处理API小结0.前言计算机视觉(ComputerVision,CV)通过研究如何令机器“看懂”世... 查看详情
vue中你不知道但却很实用的黑科技(代码片段)
...化开发中积累了不少经验。其中也有很多带有技巧性和黑科技的组件，这些特性有的是Vue文档中提到但却容易被忽略的，有的更是没有写在文档里，今天就说说Vue组件的高级玩法。写在前面本文所讲内容大多在iView项目中使用，... 查看详情
bzoj2763:[jloi2011]飞行路线分层图+spfa(代码片段)
为什么早年的题总是从0开始标号啊……又zz了一次WA分层图的题只有这一个套路吧，建分层图，然后优化时间是分层跑spfa然后层与层之间单独跑即可#include<iostream>#include<cstdio>#include<queue>#include<cstring>usingnamespaces... 查看详情
国庆出游神器：魔幻黑科技换天造物，让vlog秒变科幻大片！(代码片段)
...是人人人、车车车，该怎么办？不妨试试这个黑科技，让你的出游vlog秒变科幻大片。本文分享自华为云社区《国庆出游神器，魔幻黑科技换天造物，让vlog秒变科幻大片！》，作者：技术火炬手。国... 查看详情
p4568飞行路线分层图最短路(代码片段)
P4568飞行路线分层图最短路分层图最短路问题模型求最短路时，可有\(k\)次更改边权（减为0）思路在普通求\(Dijkstra\)基础上，\(dis[x][j]\)多开一维\(j\)以存已用了多少次机会，然后每次松弛时，做完普通松弛操作后，还要使用一次... 查看详情
最短路||分层图最短路(代码片段)
在对可以任选的一部分边或点有限制的时候，可以建分层图 HDU3499题意：n个城市有m条价格不同的航线，从s到t，可以选择一条边价格减半，求最小花费建两层图，每一层图里连边，两层图里连边#include<map>#include<queue>... 查看详情
这款黑科技，不会代码也能玩自动化，高效摸鱼(代码片段)
上篇文章推荐了一款PC端的摸鱼工具，但如果想在手机上实现自动化，并且代码能力不强，能否也能实现？答案是肯定的。今天再介绍一款Android端的系统功能增强App：Tasker，能帮助我们完成手机端的自动化操作，高效地进行摸鱼... 查看详情
abc277e-crystalswitches(分层图)(代码片段)
ABC277E-CrystalSwitches(分层图)居然忘记分层图了，菜死了！二层图，对每个有开关的连edge(i,n+i,0)edge(i,n+i,0)edge(i,n+i,0)，然后所有边权(u,v,1),(u+n,v+n,1)(u,v,1),(u+n,v+n,1)(u,v,1) 查看详情
[jloi2011]飞行路线(分层图,最短路)(代码片段)
题目链接Solution建立(k+1)层图跑(Dijkstra)就好了.Code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintmaxn=200008;intn,m,k,s,t;structsjintto;intnext;intw;a[maxn*10];inthead[maxn],size; 查看详情
hdu3499(分层图最短路or反向建图)(代码片段)
传送门方法一：分层图#include<bits/stdc++.h>#defineper(i,a,b)for(inti=a;i<=b;i++)#definemod1000000007usingnamespacestd;typedeflonglongll;constllinf=23333333333333333LL;constdoubleeps=1e-8;intT;intread() 查看详情