可并堆（实际上只有左倾树）
最近状态实在爆炸，不知为何做题真心没劲。
学了下左倾树，（二项堆到现在都没写，因为没看到有什么题是二项堆能写但是左倾树不能的= =）然后做了两道裸题：
BZOJ2333棘手的操作：= =2333。。本来想怎么用二项堆做的= =但是二项堆貌似打标记很困难的样子，然后果断写了左倾树。然后这些操作就裸了。。（第一次写的左倾树代码好丑，还是不要看的好 虽然我的代码一直很丑。。。）
#include <iostream>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define N 500050
#define INF 0x7f7f7f7f
struct Point
{
int c[2],fa,v,adv,h,sg;bool ad;
} a[N];
int n,m,add=0,t[N];
multiset <int> li;
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void adj (int x)
{
if (!x||!a[x].ad) return;
a[x].v+=a[x].adv;
a[a[x].c[0]].ad=a[a[x].c[1]].ad=1;
a[a[x].c[0]].adv+=a[x].adv;a[a[x].c[1]].adv+=a[x].adv;
a[0].ad=a[0].adv=a[x].ad=a[x].adv=0;
return;
}
inline void Down(int x)
{
adj(x);adj(a[x].c[0]);adj(a[x].c[1]);
return;
}
void DFS (int x)
{
if (a[x].fa) DFS(a[x].fa);Down(x);
return;
}
int Merge(int x,int y)
{
if (!x||!y) return x+y;
Down(x);Down(y);
if (a[y].v>a[x].v)
swap(x,y);
a[x].c[1]=Merge(a[x].c[1],y);a[a[x].c[1]].fa=x;
a[x].h=min(a[a[x].c[1]].h,a[a[x].c[0]].h)+1;
if (a[x].h!=a[a[x].c[1]].h+1)
swap(a[x].c[0],a[x].c[1]);
return x;
}
inline void Line (int x,int y)
{
while (a[x].fa) x=a[x].fa;
while (a[y].fa) y=a[y].fa;
if (x==y) return;
li.erase(li.lower_bound(-a[x].v));
li.erase(li.lower_bound(-a[y].v));
li.insert(-a[Merge(x,y)].v);
return;
}
int main()
{
int i,j,k,l,q,w,e;
set <int> :: iterator it;
char b[20];li.clear();
scanf("%d",&n);a[0].v=INF;a[0].h=0;
for (i=1;i<=n;i++)
a[i].v=Read(),a[i].c[0]=a[i].c[1]=a[i].ad=a[i].adv=
a[i].fa=a[i].ad=0,a[i].h=1,li.insert(-a[i].v),
t[i]=a[i].sg=i;
scanf("%d",&m);
for (i=1;i<=m;i++)
{
scanf("%s",b);
if (b[0]=='F')
{
if (b[1]=='1')
DFS(k=t[Read()]),printf("%d\n",a[k].v+add);else
if (b[1]=='2')
{
k=Read();
while (a[k].fa) k=a[k].fa;
printf("%d\n",a[k].v+add);
}else printf("%d\n",-*li.begin()+add);
}else
if (b[0]=='A')
{
if (b[1]=='3') add+=Read();else
if (b[1]=='2')
{
k=Read();
while (a[k].fa) k=a[k].fa;
a[k].ad=1;a[k].adv=Read();
li.erase(li.lower_bound(-a[k].v));
Down(k);
li.insert(-a[k].v);
}else
{
DFS(k=t[Read()]);l=Read();
if (l<0)
{
w=a[k].fa;
if (!w) li.erase(li.lower_bound(-a[k].v));
a[k].v+=l;
while (1)
{
Down(k);
q=a[k].c[!a[k].c[0]||(a[k].c[1]&&a[k].
c[0]&&a[a[k].c[1]].v>a[a[k].c[0]].v)];
if (q&&a[q].v>a[k].v)
swap(a[q].v,a[k].v),
swap(a[q].sg,a[k].sg),
swap(t[a[q].sg],t[a[k].sg]),k=q;else
break;
}
if (!w)
{
while (a[k].fa) k=a[k].fa;
li.insert(-a[k].v);
}
}else
if (!a[k].fa)
{
li.erase(li.lower_bound(-a[k].v));
a[k].v+=l;li.insert(-a[k].v);
}else
{
a[k].v+=l;
while (a[k].v>a[a[k].fa].v&&a[a[k].fa].fa)
swap(a[k].v,a[a[k].fa].v),
swap(a[k].sg,a[a[k].fa].sg),
swap(t[a[k].sg],t[a[a[k].fa].sg]),
k=a[k].fa;
if (a[k].v>a[a[k].fa].v)
li.erase(li.lower_bound(-a[a[k].fa].v)),
li.insert(-a[k].v),
swap(a[k].v,a[a[k].fa].v),
swap(a[k].sg,a[a[k].fa].sg),
swap(t[a[k].sg],t[a[a[k].fa].sg]);
}
}
}else
Line(Read(),Read());
}
return 0;
}
BZOJ2809dispatching：据说是P神那届APIO的题，感觉还是很裸，我写了左倾树启发式合并。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
#define ll long long
ll ans=0,t[N];
int n,m,v[N],fa[N],c[N][2],fi[N],ne[N],gf[N],h[N],sum[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline int Merge(int x,int y)
{
if (!x||!y) return x+y;
if (v[x]<v[y]) swap(x,y);
c[x][1]=Merge(c[x][1],y);fa[c[x][1]]=x;
h[x]=min(h[c[x][0]],h[c[x][1]])+1;
if (h[x]!=h[c[x][1]]+1)
swap(c[x][1],c[x][0]);
return x;
}
inline int Pop(int x)
{
int i=v[gf[x]];
gf[x]=Merge(c[gf[x]][0],c[gf[x]][1]);fa[gf[x]]=0;
return i;
}
int DFS(int x)
{
int i,j,k,l,q,w,e;ll s=0;
gf[x]=x;h[x]=1;s=v[x];sum[x]=1;
for (i=fi[x];i;i=ne[i])
{
s+=DFS(i);gf[x]=Merge(gf[i],gf[x]);sum[x]+=sum[i];
}
while (s>m) s-=Pop(x),sum[x]--;
ans=max(t[x]*sum[x],ans);
return s;
}
int main()
{
int i,j,k,l,q,w,e;
memset(v,0,sizeof(v));memset(t,0,sizeof(t));
memset(c,0,sizeof(c));memset(h,0,sizeof(h));
memset(fi,0,sizeof(fi));memset(ne,0,sizeof(ne));
memset(gf,0,sizeof(gf));memset(fa,0,sizeof(fa));
memset(sum,0,sizeof(sum));
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
fa[i]=Read(),v[i]=Read(),t[i]=Read(),
ne[i]=fi[fa[i]],fi[fa[i]]=i;
DFS(1);
printf("%lld\n",ans);
return 0;
}
还有道题跟可并堆并没有什么关系的：
BZOJ1078斜堆：思路也都想的差不多，但是感觉自己就是集中不了注意力，感觉一直在胡思乱想，然后就直接翻题解去了，这种状态还怎么愉快地玩耍啊！其实感觉好像是晚饭吃太饱了= =可以发现最后删除的结点一定在当前树一直往左的路径上，并且不会有右子树，并且一定是这些点中深度最小的（还有种情况是左路径上存在两个没有右子树的点互为父子则选叶子结点的那个），这些性质都十分可证。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 205
#define INF 0x7f7f7f7f
int fa[N],gf=0,c[N][2],n,m,li[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int DFS(int x)
{
int i;
if (!c[x][1]&&(!c[x][0]||c[c[x][0]][0]+c[c[x][0]][1]))
{
if (fa[x])
c[fa[x]][0]=c[x][0];else
gf=c[x][0];
fa[c[x][0]]=fa[x];
return x;
}
i=DFS(c[x][0]);swap(c[x][0],c[x][1]);
return i;
}
int main()
{
int i,j,k,l,q,w,e;
memset(fa,0,sizeof(fa));memset(c,0,sizeof(c));
scanf("%d",&n);gf=n+1;
for (i=1;i<=n;i++)
{
k=Read();
if (k<100) c[k][0]=i;else c[k-=100][1]=i;
fa[i]=k;
}
c[n+1][0]=c[0][0];c[n+1][1]=c[0][1];
fa[c[n+1][0]]=n+1;fa[c[n+1][1]]=n+1;
c[0][0]=c[0][1]=0;
for (i=1;i<=n+1;i++)
li[n+1-i]=DFS(gf);
for (i=0;i<=n;i++)
printf("%d ",li[i]==n+1?0:li[i]);
printf("\n");
return 0;
}
BZOJ4003城池攻占：裸的打标记左倾树，一开始写丑了，加了一堆不必要的东西，然后不想重写，于是一直改一直wa，后来重写之后又wa了几次终于过了。代码能力是硬伤！
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300050
#define INF 0x7f7f7f7f
#define ll long long
int s[N],ss[N],gf[N],n,m,as[N],h[N];
int c[N][2],fi[N],ne[N],ff[N],nf[N],a[N];
ll v[N],t[N],ad[N],xj[N],r[N];
inline ll Read()
{
ll x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void Down(int x)
{
if (!x) return;
if (xj[x]!=1)
{
t[x]*=xj[x];ad[c[x][0]]*=xj[x];ad[c[x][1]]*=xj[x];
xj[c[x][0]]*=xj[x];xj[c[x][1]]*=xj[x];xj[x]=1;
}
if (ad[x])
{
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];ad[x]=0;
}
if (as[x])
{
s[x]+=as[x];as[c[x][0]]+=as[x];as[c[x][1]]+=as[x];as[x]=0;
}
return;
}
int Merge(int x,int y)
{
if (!x||!y) return x+y;
Down(x);Down(y);
if (t[x]>t[y]) swap(x,y);
c[x][1]=Merge(c[x][1],y);
h[x]=min(h[c[x][1]],h[c[x][0]])+1;
if (h[x]!=h[c[x][1]]+1) swap(c[x][0],c[x][1]);
return x;
}
inline void Pop(int x)
{
ss[x]++;gf[x]=Merge(c[gf[x]][0],c[gf[x]][1]);
return;
}
void DFS(int x)
{
for (int i=ff[x];i;i=nf[i])
gf[x]=Merge(gf[x],i);
for (int i=fi[x];i;i=ne[i])
DFS(i),gf[x]=Merge(gf[x],gf[i]);
while (Down(gf[x]),t[gf[x]]<v[x]&&gf[x]) Pop(x);
if (!gf[x]) return;Down(gf[x]);
if (a[x]) xj[gf[x]]=r[x];else ad[gf[x]]=r[x];
as[gf[x]]=1;
return;
}
int main()
{
int i,j,k,l,q,w,e;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) v[i]=Read();
for (i=2;i<=n;i++)
ne[i]=fi[k=Read()],fi[k]=i,a[i]=Read(),r[i]=Read();
for (i=1;i<=m;i++)
t[i]=Read(),nf[i]=ff[k=Read()],ff[k]=i,xj[i]=h[i]=1;
v[0]=(ll)(1e18);
fi[0]=1;DFS(0);
for (i=1;i<=n;i++)
printf("%d\n",ss[i]);
for (i=1;i<=m;i++)
printf("%d\n",s[i]);
return 0;
}
可并堆也更到这里算了，话说右边那个播放器感觉蛮好玩的于是搞了一个，把看过的一些番的不错的OP、ED、人物歌什么的放上来了，Claris赛高！
网络流题汇总
最近一直在做网络流相关，于是都放上来了= =
BZOJ2127happiness：最小割
BZOJ3144切糕：最小割
BZOJ1497最大获利：胡BT论文题，裸最大权闭合子图。
BZOJ1443游戏Game：首先黑白染色构二分图，然后二分图中所有不一定在最大匹配中的点就是所求的答案。证明之类的细节详见CYB2015年论文
BZOJ2229最小割：图中的最小割两两不相交，然后n次最小割就可以了。
BZOJ2039employ人员雇佣：最小割
BZOJ2150部落战争：最小路径覆盖，网络流可以拆入点出点，S往出点连1，入点往T连1，中间的边INF，用点数-C[S,T]。或者直接Hungary
SPOJ Optimal Marks (OPTM)：胡BT论文题，按位跑网络流
BZOJ1066蜥蜴：最大流
BZOJ1433假期的宿舍：被模糊不清的题意坑了n次，而且^跟＾还有区别= =真心caodan。裸的二分图匹配，我用网络流写的= =
BZOJ1797Mincut最小割：貌似是跑一遍最小割，然后再残量网络中跑一遍强连通分量。设这条边的两端为u和v，如果这条边满流而且u和S在同一强连通分量里面且v和T在同一强连通分量里面就说明这条边必须割（试着给这条边增大流量限制显见）。如果这条边满流而且u和v不在同一强连通分量里面就说明这条边可以割。（真心不会证，网上也没什么好的证明= =跟duyege想了好久也是伪证）
BZOJ1266上学路线route：建最短路图然后跑最小割= =（然后这题时限caodan我换了几种姿势始终跑不过= =不知为何感觉我的dinic就是要比别人常数大）
BZOJ3504危桥：结论题，网上的题解都是些什么：“如果直接S连a1、b1，a2、b2连T，可能会a1流到b2、b1流到a2，所以要将起点换成b2，终点换成b1再跑一遍看两次是不是都是满流”，看上去好像“显而易见”一样，靠谱的证明一个都没有TATQAQ2333。
BZOJ1412狼和羊的故事：最小割
BZOJ1305跳舞dance：二分答案，拆点，给连坏边的点加上限制k，所有二分图中的边权为1，然后跑最大流= =
BZOJ1189紧急疏散：对于门按时间拆点，如果空地上这个人可以走到这个门就往这个门的那个时候连边，二分时间后每个门的当前时间t往t+1连INF。
BZOJ1822 Frozen Nova 冷冻波：建图很水，暴力连边然后二分答案跑网络流，但是计算几何真心caodan，而且貌似如果巫妖和小精灵与树相切是可以打到的。。。
BZOJ2756奇怪的游戏：显然如果n*m为偶数并且黑白染色后黑格之和不等于白格之和则无解，还有n*m为奇数并且黑白染色后黑格之和减去白格之和比最大值要小也是无解的。否则将图重建成二分图，然后二分答案网络流验证答案。如果学我的dinic不敢加优化会一直T一直T一直T= =
BZOJ1143祭祀：果然最近太颓了么= =一直没有看出来。传递闭包+最长反链（即最小链覆盖，即总点数-拆点后可达两点连边的二分图匹配数，YY可证）
为了方便，一条边的流量fi和费用vi用{fi,vi}表示
BZOJ1834网络扩容：第一问水过，第二问在残量网络上再给原图每条边复制一条流量INF、费用不变的边，残量网络无费用。
BZOJ1221软件开发：费用流，理解这么久我真是废到一定境界了，但确实感觉费用流比最小割的题目要caodan些= =。每个点拆成xi和yi，分别代表第i天的好毛巾和没洗毛巾，则S往xi连{ni,0}，S往yi连{INF,f}，yi往T连{ni,0}，xi往xi+1连{INF,0}，xi往y(i+a+1)连{INF,fa}，xi往y(i+b+1)连{INF,fb}，然后跑一遍。
BZOJ2661连连看：费用流。好神（keng）的题，看上去是一般图最大权匹配，实际上测试了一下才知道是二分图= =然后就黑白染色，暴力建图跑了。。（补：后来跑了一下大数据，然后这性质就果断不成立了，网上的什么拆点的如果碰到这种奇环也貌似是会挂的= =出题人sxbk）
BZOJ2424订货：费用流：拆点都不需要，很水的建图。
BZOJ2597剪刀石头布：费用流：确实很经典的题，很屌的建图。设每个点胜的场数为d[i]，则ans=C(n,3)-ΣC(d[i],2)，自行脑补。。然后化下式子变成C(n,3)+C(n,2)/2-Σd[i]^2/2，所以就对每个比赛建个点并且向T连{1,0}的边，每个点向它可能会胜利的比赛连{1,0}，S向每个点连{1,1}、{1,3}、{1,5}……这样可以保证是d[x]^2，然后跑费用流结果就是Σd[i]^2。
BZOJ1927星际竞速：费用流，最小权值路径覆盖。想了好久真是羞耻，就是拆点成Ui、Vi之后S往Ui连{1,0}，S往Vi连{1,Ai}，Vi往T连{1,0}，然后原图中的边i->j,w就连Ai往Bj连{1,w}，然后直接跑。
然后除了两个wa了n久的坑等着填，还有单纯性、zkw费用流什么的没学，网络流相关的东西就先搞到这里了。
现在貌似没什么很多时间了= =接下来是背堆模板？
算了感觉费用流的比例有点不太和谐，在颓废一个晚上算了= =应该不会拖进度吧。。。
不管了接着更，话说晚上状态真心不好：
BZOJ1930吃豆豆：看上去很裸，但是一来卡内存，二来卡时间，如果暴力建边会有n^2规模。（madan HZWER把把暴力建边的代码放到博客里面了，搞得我还一直以为这种暴力没人卡的。。。）反正就是要加优化：原来是对于每个点拆点然后流量限制都是1，但是现在允许一个点被走两次，但其中只算一次的豆豆，然后如果存在三个点a->b->c则a不往c连边，这样就可以跑出来了。这个正确性还算比较显然吧。。。
BZOJ1877晨跑：裸建图费用流
BZOJ3171循环格：反正每个点的入度都要为1，所以拆点，每两个相邻点相连，然后如果这条边原图中存在则费用为0否则为1，然后每个出点往T连1。
BZOJ2245工作安排：裸建图，一开始看错题了真是羞耻。。
BZOJ1070修车：把技术人员按倒数第几修的车拆点，然后连边跑跑跑！
BZOJ2879美食节：真心屌！虽然题目意思跟上题一毛一样，但是数据扩大了n倍，于是考虑优化连边，如果一个厨师倒数第k个还没流就不可能会流倒数第k+1个，于是动态连边，如果k满流了就建k+1的边。
BZOJ1565植物大战僵尸：最大权闭合子图乱入！很容易看出来是这个模型。同时还要注意有的点永远到不了，所以要先拓扑排序搞一波。
这次是真的不更了！
ZJOI2015Day2酱油记
算是去混了两天课，滚了半天粗，然后回来了。。
走之前下1080P的番，下了一晚上系统直接exploded，然后就没带电脑。结果书也忘记带几本了，结果晚上还有火车上各种无聊。本来还有电视，但是尼玛跟XL一间房！！！补番也不能补，代码也敲不成，整个人都要爽飞了。结果回学校zeiye的BZOJ刷题记录直接多了三版，我要报警了！那些书还有论文省吃俭用总算是熬过去了，组合数学出了还有两章练习其实都看得差不多了（其实图论还有前面的相异代表系什么的鬼都是一路跳着看的= =）
然后白天听了两天课，一路半睡半听。也算是脸熟了浙江的几个大爷。感觉大多都是杂题还有什么题选讲= =尤其是学军的大爷都是杂题选讲。除了一开始的王鉴浩大爷讲的那个boarder tree全程高能（说白了就是太弱听不懂）
白天还一直碰到yali的大爷，默默orzei了两下。听说ZJOI已经变成全国性赛事了，湖南好像就来了yali、changjun、SDFZ还有衡八好像也来了？听说其他省好像也来了好多，反正我只认得那个新疆大爷= =（在哪里都碰得到，膜膜膜！）
考试那天算是体会到了linux机房的快感！开考前发现左边坐着毛爷爷，快要吓飞了= =而且贴错了标签，我还乡霸地一直在问毛爷爷是不是坐错了位置TATQAQ2333。后来开考了，结果压缩包各种打不开，后来是8:10开考的= =。当然比较良心的是还会发面包，正好没吃早饭= =而且还有隔板这种东西的存在，各种高端！但是题目一点都不良心（说白了还是弱啊），第一题提答，翻译题，果断弃疗先看其他题。第二题什么ax^2+bx还要求最小代价，果断写了30分给的费用流然后弃疗，由于人太弱，还是第一次写费用流，但愿没什么caodan的细节。第三题看着就不禁想到了二分图，然后脑补各种二分图做法，然后不会啊不会啊不会啊，总觉得是自己姿势水平不够，总觉得是种什么高端的二分图做法= =但尼玛除了是二分图之外还有其他的性质啊！然后果断写了10分暴力，然后就滚去玩提答了。然后就真的是滚了= =因为没用过linux，考场上面不会用终端（说白了就是智商不够）后来就写了个翻译器然后肉眼大法好，但是没有终端果然还是感觉比较虚= =下考之后听wulala说第三题wifi放在一边的话可以直接DP，后来脑补了一下感觉非常有道理啊！考场上面一直都没往DP想= =果然还是都要考虑啊
后来成绩出来50分拿好滚粗了，提答题还是虚了= =。毕竟人太弱。而且最近感觉真心萎废爆了= =而且不仅是萎废，感觉最近一直比较背，用什么电脑什么电脑出问题，而且还有一个U盘无端坏掉了，手机充电器也一直没找到，反正各种背时，结果真心悲伤的是LAccelerator被逼退了，明明联赛都还没到，明明罗大神这么努力，为毛就半天时间就这么突然退掉了！而我也什么都做不到。。。只能但愿罗大神文化安好吧，至少我留下来的这段时间，我也会努力的。
另外把那几篇网络流的整理成一篇吧，总感觉这样搞还是不行= =
计划
感觉最近一直在做最小割的题真是浪够了。
下周如果有时间就刷完费用流好了。。
开始要学东西了：CYB讲匹配的论文里面的东西都要啃掉，匹配、网络流这些东西搞完之后就开始搞数学。先把必修四自主学习册做掉，主要是KZF还有VFK的数学课件都放在那里好久没管，做数学题完全就是看题跑。然后开始下一个做专题，可以做做BZOJ做做CF的数学题，听罗大神说CF的数学题不错。组合数学这个学期推完啊！推完就看初等数论。还有要学的：高斯消元、斯坦纳树要写一遍、拟阵、算导的矩阵那一章要推了、FFT、莫队（这东西留到现在都没写是有多废！）还有什么的都学了！下面几个大专题：字符串，计算几何，数据结构（还有分治什么的），动归，图论。反正先把这些常用的东西都学掉，希望尽快搞完吧。现在刷起题来真心不爽，有的时候知道正解不会写，或者是知道标算不能更正= =
这些搞完之后然后就可以多去刷点题刷点其他的东西了。
想想从高一入学到现在浪了将近一年了！虽然还是有进步吧，但是明显慢了啊！
想想之前自己怎么这么乐观，总觉得还是有时间的，然后就一直浪到现在，现在都不知道还能不能赶上了。。只能努力吧。
5.29更：en真心只剩下一个半月了= =有的东西先延后算了，先把可能考的东西要学一下，然后把往届的题刷掉。先是小狗之前讲的二项堆什么的鬼，然后就搞数学，先把vfk、kzf的课件刷完，然后是把LAccelerator的题刷掉一些，好像Gromah那里也有些题屯在那里的。然后是立体几何，首先dyf的课件刷完，然后刷刷刷，这些搞完至少要在6月十几号之前吧，但愿搞得完。然后是高斯消元，然后搞些数据结构的题刷下（但是好像刷起来很耗时间）忘记了字符串的题也要搞搞。反正至少一些比较基础的应用要知道些啊！
反正努力吧
分层图
终于不是网络流了= =
BZOJ2763/2662
题意都差不多，代码都只差一点= =：都是在一个无向图中，你一共有k次改变一条边上的权值的机会，求最短路= =（两道题在细节上有一点区别= =）
做法：拆成k个点，然后再跑最短路= =，貌似叫做分层图。
2763：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 100050
#define INF 0x7f7f7f7f
struct Point
{
int a1,a2;
};
queue <Point> a;
int fi[N],c[M][3],h[N][20],n,m,v,S,T,ss=0;
bool b[N][20];
inline int Read()
{
int x=0;char y;
do y=getchar();while (y<'0'||y>'9');
do x=(x << 3)+(x << 1)+y-'0',y=getchar();
while (y>='0'&&y<='9');
return x;
}
inline void Line (int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
return;
}
int main()
{
int i,j,q,w,e;
Point k,l;
memset(c,0,sizeof(c));memset(h,0,sizeof(h));
memset(fi,0,sizeof(fi));memset(b,0,sizeof(b));
scanf("%d%d%d%d%d",&n,&m,&v,&S,&T);
for (i=1;i<=m;i++)
q=Read(),w=Read(),e=Read(),Line(q,w,e);
for (i=0;i<n;i++)
for (j=0;j<=v;j++)
h[i][j]=INF;
h[S][0]=0;k.a1=S;k.a2=0;a.push(k);b[S][0]=1;
while (!a.empty())
{
k=a.front();
for (i=fi[k.a1];i;i=c[i][1])
{
if (h[c[i][0]][k.a2]>c[i][2]+h[k.a1][k.a2])
{
h[c[i][0]][k.a2]=c[i][2]+h[k.a1][k.a2];
if (!b[c[i][0]][k.a2])
b[c[i][0]][k.a2]=1,l=k,l.a1=c[i][0],
a.push(l);
}
if (k.a2<v&&h[c[i][0]][k.a2+1]
>h[k.a1][k.a2])
{
h[c[i][0]][k.a2+1]=h[k.a1][k.a2];
if (!b[c[i][0]][k.a2+1])
b[c[i][0]][k.a2+1]=1,l=k,l.a1=c[i][0],l.a2++,
a.push(l);
}
}
a.pop();b[k.a1][k.a2]=0;
}
e=INF;
for (i=0;i<=v;i++)
e=min(e,h[T][i]);
printf("%d\n",e);
return 0;
}
2662：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 100050
#define INF 0x7f7f7f7f
struct Point
{
int a1,a2;
};
queue <Point> a;
int fi[N],c[M][3],h[N][20],n,m,v,S,T,ss=0;
bool b[N][20];
inline int Read()
{
int x=0;char y;
do y=getchar();while (y<'0'||y>'9');
do x=(x << 3)+(x << 1)+y-'0',y=getchar();
while (y>='0'&&y<='9');
return x;
}
inline void Line (int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
return;
}
int main()
{
int i,j,q,w,e;
Point k,l;
memset(c,0,sizeof(c));memset(h,0,sizeof(h));
memset(fi,0,sizeof(fi));memset(b,0,sizeof(b));
scanf("%d%d%d",&n,&m,&v);S=1;T=n;
for (i=1;i<=m;i++)
q=Read(),w=Read(),e=Read(),Line(q,w,e);
for (i=1;i<=n;i++)
for (j=0;j<=v;j++)
h[i][j]=INF;
h[S][0]=0;k.a1=S;k.a2=0;a.push(k);b[S][0]=1;
while (!a.empty())
{
k=a.front();
for (i=fi[k.a1];i;i=c[i][1])
{
if (h[c[i][0]][k.a2]>c[i][2]+h[k.a1][k.a2])
{
h[c[i][0]][k.a2]=c[i][2]+h[k.a1][k.a2];
if (!b[c[i][0]][k.a2])
b[c[i][0]][k.a2]=1,l=k,l.a1=c[i][0],
a.push(l);
}
if (k.a2<v&&h[c[i][0]][k.a2+1]
>h[k.a1][k.a2]+c[i][2]/2)
{
h[c[i][0]][k.a2+1]=h[k.a1][k.a2]+c[i][2]/2;
if (!b[c[i][0]][k.a2+1])
b[c[i][0]][k.a2+1]=1,l=k,l.a1=c[i][0],l.a2++,
a.push(l);
}
}
a.pop();b[k.a1][k.a2]=0;
}
e=INF;
for (i=0;i<=v;i++)
e=min(e,h[T][i]);
printf("%d\n",e);
return 0;
}
