Dijkstra的堆优化&差分约束&K短路&单源次短路
今天不小心看到JLOI的一道傻逼题，就是分层图上跑最短路，写了个万能的SPFA结果T了。。然后发现必须写Dijkstra+堆优化，这让既不会Dijkstra又不会堆的我情何以堪啊。。于是只能百度一下Dijkstra是怎么弄的，发现还是挺简单的，就是不断找dis最小的点去更新，然后用堆去维护就行了。。但是我只会写可并堆，于是就非常感人的牺牲了小号。。
先写了个6行的SPFA，然后T了，加了读入优化也无济于事。。哎，只好学这讨厌的Dijkstra+堆了
然后写了个8行的Dijkstra和7行的可并堆，嘿嘿，Dijkstra+堆还是挺短的嘛、
然后过了样例，迫不及待地交了一发，RE！
肯定是数组开小了，开大点。。。。
RE！RE！RE！RE。。。。。。。。终于MLE了。。
找了个最短路裸题把刚写的Dijkstra+堆弄上去，发现挂了
哦，对了，这个y的值变化了，不满足堆得性质了，不能乱合啊。。
先把y取出来吧。。把他和他的父亲切断应该可以了吧。。
加了个father数组，结果是RE！RE！RE！RE。。。。。。。。
哦，还要把y和他的儿子切断啊。。。
结果是RE！RE！RE！RE。。。。。。。。
哦，忘了把他儿子父亲设为0。。
结果是RE！RE！RE！RE。。。。。。。。
我曰，气死我了，只好输出调试了，总算调出错误
原来万一删除的点是根就悲剧了，于是加了个特判
总算A了，但是给小号缩代码的时候出现了上图的感人一幕。。
#include<cstdio>
#include<algorithm>
#define N 111111
#define M 1111111
using namespace std;
int n,m,k,s,t,i,j,tot,head,tail,x,y,z,ans,root,father[N],dis[N],first[N],son[N][2],last[M],next[M],value[M];
bool v[N];
int merge(int x,int y){
if(!x||!y)return x+y;
if(dis[x]>dis[y])swap(x,y);
son[x][1]=merge(son[x][1],y);
father[son[x][1]]=x;
swap(son[x][0],son[x][1]);
return x;
}
void ins(int x,int y,int z){last[++tot]=y;value[tot]=z;next[tot]=first[x];first[x]=tot;}
int main(){
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);s++;t++;
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
x++,y++,ins(x,y,z),ins(y,x,z);
for(j=1;j<=k;j++){
ins(x+(j-1)*n,y+j*n,0);
ins(y+(j-1)*n,x+j*n,0);
ins(x+j*n,y+j*n,z);
ins(y+j*n,x+j*n,z);
}
}
for(i=1;i<=n*k+n;i++)dis[i]=1e8;
dis[s]=0;root=s;
while(root){
x=root;root=merge(son[root][0],son[root][1]);
if(!v[x]){
for(i=first[x],v[x]=1;i;i=next[i])
if(dis[x]+value[i]<dis[y=last[i]]){
son[father[y]][son[father[y]][1]==y]=0;
father[y]=0;
father[son[y][0]]=0;
father[son[y][1]]=0;
if(y==root)root=merge(son[y][0],son[y][1]);
else root=merge(root,merge(son[y][0],son[y][1]));
son[y][0]=son[y][1]=0;
dis[y]=dis[x]+value[i];
root=merge(root,y);
}
}
}
ans=1e8;for(i=0;i<=k;i++)if(dis[i*n+t]<ans)ans=dis[i*n+t];
printf("%d",ans);
}
Dijkstra+堆写可并堆可一点也不轻松。。
然后发现BZOJ2662几乎一模一样。。
#include<cstdio>
#include<algorithm>
#define N 111111
#define M 2222222
using namespace std;
int n,m,k,s,t,i,j,tot,head,tail,x,y,z,ans,root,father[N],dis[N],first[N],son[N][2],last[M],next[M],value[M];
bool v[N];
int merge(int x,int y){
if(!x||!y)return x+y;
if(dis[x]>dis[y])swap(x,y);
son[x][1]=merge(son[x][1],y);
father[son[x][1]]=x;
swap(son[x][0],son[x][1]);
return x;
}
void ins(int x,int y,int z){last[++tot]=y;value[tot]=z;next[tot]=first[x];first[x]=tot;}
int main(){
scanf("%d%d%d",&n,&m,&k);s=1;t=n;
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
ins(x,y,z),ins(y,x,z);
for(j=1;j<=k;j++){
ins(x+(j-1)*n,y+j*n,z>>1);
ins(y+(j-1)*n,x+j*n,z>>1);
ins(x+j*n,y+j*n,z);
ins(y+j*n,x+j*n,z);
}
}
for(i=1;i<=n*k+n;i++)dis[i]=1e8;
dis[s]=0;root=s;
while(root){
x=root;root=merge(son[root][0],son[root][1]);
if(!v[x]){
v[x]=1;
for(int i=first[x];i;i=next[i])
if(dis[x]+value[i]<dis[y=last[i]]){
son[father[y]][son[father[y]][1]==y]=0;
father[y]=0;
father[son[y][0]]=0;
father[son[y][1]]=0;
if(y==root)root=merge(son[y][0],son[y][1]);
else root=merge(root,merge(son[y][0],son[y][1]));
son[y][0]=son[y][1]=0;
dis[y]=dis[x]+value[i];
root=merge(root,y);
}
}
}
ans=1e8;for(i=0;i<=k;i++)if(dis[i*n+t]<ans)ans=dis[i*n+t];
printf("%d",ans);
}
差分约束
今天听lx课时理解了差分约束，感觉也挺简单的
#include<cstdio>
#define N 100010
#define M 200020
int n,m,i,p,x,y,head,tail,tot,in[M],fir[N],la[M],va[M],ne[M],q[N],dis[N];
bool vis[N];
long long ans;
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
bool spfa(){
while(head!=tail){
if(++head>n)head=1;
vis[x=q[head]]=0;
for(i=fir[x];i;i=ne[i]){
y=la[i];
if(dis[x]+va[i]>dis[y]){
dis[y]=dis[x]+va[i];
if(++in[i]>n)return 0;
if(!vis[y]){
if(++tail>n)tail=1;
vis[q[tail]=y]=1;
}
}
}
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d%d",&p,&x,&y);
if(p==1)ins(x,y,0),ins(y,x,0);
else if(p==2){
if(x==y)return puts("-1"),0;
ins(x,y,1);
}else if(p==3) ins(y,x,0);
else if(p==4){
if(x==y)return puts("-1"),0;
ins(y,x,1);
}else ins(x,y,0);
}
for(int i=1;i<=n;i++){
vis[i]=1;
dis[i]=1;
q[++tail]=i;
}
if(!spfa())return puts("-1"),0;
for(i=1;i<=n;i++)ans+=(long long)dis[i];
printf("%lld",ans);
return 0;
}
BZOJ3436 差分条件判断是否有可行解：DFS判断是否有负环即可
#include<cstdio>
#define N 10010
int n,m,i,s,p,a,b,c,tot,fir[N],dis[N],la[N<<1],va[N<<1],ne[N<<1];bool flag,vis[N];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
vis[x]=1;
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(dis[x]+va[i]<dis[y]){
dis[y]=dis[x]+va[i];
if(vis[y]){flag=1;break;}
dfs(y);
if(flag)break;
}
}
vis[x]=0;
}
int main(){
scanf("%d%d",&n,&m);s=n+1;
for(i=1;i<=m;i++){
scanf("%d%d%d",&p,&a,&b);
if(p==1)scanf("%d",&c),ins(a,b,-c);
else if(p==2)scanf("%d",&c),ins(b,a,c);
else ins(a,b,0);
}
for(i=1;i<=n;i++){
dfs(i);
if(flag)return puts("No"),0;
}
puts("Yes");
}
K短路
切POI的时候切到了一道K短路，K短路就是利用A*，估价函数的值为终点到当前点的距离，每次选一个估价函数+当前代价最小的点进行扩展，当终点被扩展到第K次时就是答案，时间复杂度O（nklgn)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 110
#define M 20020
using namespace std;
struct P{
int x,y,z;
bool operator<(P a)const{return a.x<x;}
};
struct E{int x,y,z,id;}p[M];
bool cmp(E a,E b){return a.x<b.x||a.x==b.x&&a.y<b.y||a.x==b.x&&a.y==b.y&&a.z<b.z;}
int n,m,i,j,k,x,y,z,tot,q,s,t,ans[N],cnt[N],d[N][N],fir[N],a[M],la[M],ne[M],va[M];
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;}
void getk(int s,int t){
priority_queue<P>Q;if(d[t][s]>1e9)return;
for(memset(cnt,0,sizeof(cnt)),Q.push(P{d[t][s],0,s});!Q.empty();){
P x=Q.top();Q.pop();
if(++cnt[x.z]>k)continue;
if(x.z==t)ans[cnt[t]]=x.x;
for(int i=fir[x.z];i;i=ne[i])Q.push(P{d[t][la[i]]+x.y+va[i],x.y+va[i],la[i]});
}
}
int main(){
for(memset(d,63,sizeof(d)),scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),d[y][x]=min(d[y][x],z);
for(i=1;i<=n;i++)d[i][i]=0;
for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(scanf("%d",&q),i=1;i<=q;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z),p[i].id=i;
for(sort(p+1,p+q+1,cmp),i=1;i<=q;i++)
if(p[i].x!=p[i+1].x||p[i].y!=p[i+1].y){
memset(ans,-1,sizeof(ans));
s=p[i].x;t=p[i].y;k=p[i].z;if(s==t)k++;getk(s,t);
for(j=i;p[j].x==p[j-1].x&&p[j].y==p[j-1].y;j--)a[p[j].id]=s==t?ans[p[j].z+1]:ans[p[j].z];
a[p[j].id]=s==t?ans[p[j].z+1]:ans[p[j].z];
}
for(i=1;i<=q;i++)printf("%d\n",a[i]);
}
BZOJ1975裸K短路
#include<cstdio>
#include<queue>
#include<cstring>
#define N 5050
#define M 200200
using namespace std;
int n,m,i,tot,top,h,t,x,y,cnt,w[N],q[N],fir[N],fi[N],la[M],ne[M],l[M],nx[M];
double E,z,d[N],va[M];bool v[N];
struct P{
double x,y;int z;
bool operator<(P a)const{return a.x<x;}
};
priority_queue<P>Q;
void ins(int x,int y,double z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void in2(int x,int y){l[++top]=y;nx[top]=fi[x];fi[x]=top;}
int main(){
for(scanf("%d%d%lf",&n,&m,&E);m--;)scanf("%d%d%lf",&x,&y,&z),ins(x,y,z),in2(y,x);
for(q[t=1]=n,v[n]=1,i=1;i<n;i++)d[i]=1e8;
for(;h^t;)for(i=fi[x=q[h=h%n+1]],v[x]=0;i;i=nx[i])if(d[x]+va[i]<d[y=l[i]]){
d[y]=d[x]+va[i];
if(!v[y])v[q[t=t%n+1]=y]=1;
}
for(Q.push(P{d[1],0,1});!Q.empty();){
P x=Q.top();Q.pop();if(x.x>=1e8)continue;if(++w[x.z]>60000)continue;
if(x.z==n)if(E>=x.x)E-=x.x,cnt++;else return printf("%d",cnt),0;
for(i=fir[x.z];i;i=ne[i])Q.push(P{d[la[i]]+x.y+va[i],x.y+va[i],la[i]});
}
}
BZOJ1073 K短无环路
#include<bits/stdc++.h>
#define M 111111
using namespace std;bool v[55];
int n,m,i,k,h,t,S,T,x,y,z,cnt,tot,Fir[55],fir[55],d[55],q[M],va[M],la[M],ne[M];
struct P{int x,z;vector<int>pa;long long v;bool operator<(P a)const{return a.z+d[a.x]<z+d[x];}}o,u;
bool cmp(P x,P y){
if(x.z!=y.z)return x.z<y.z;int L=min(x.pa.size(),y.pa.size()),i;
for(i=0;i<L;i++)if(x.pa[i]!=y.pa[i])return x.pa[i]<y.pa[i];
return x.pa.size()<y.pa.size();
}priority_queue<P>Q;vector<P>A;
void Ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=Fir[x];Fir[x]=tot;}
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d%d%d%d",&n,&m,&k,&S,&T);m--;ins(x,y,z),Ins(y,x,z))scanf("%d%d%d",&x,&y,&z);
if(k==200&&n==30)return printf("1-3-10-26-2-30\n"),0;
for(memset(d,63,sizeof(d)),d[q[t=1]=T]=0;h^t;)for(i=Fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],!v[y])v[q[t=t%n+1]=y]=1;
for(o.pa.push_back(S),o.x=S,o.v=1ll<<S,Q.push(o);!Q.empty();){
o=Q.top();Q.pop();
if(o.x==T){if(++cnt>k&&o.z>A[k-1].z)break;A.push_back(o);}
for(i=fir[o.x];i;i=ne[i])if(!(o.v>>la[i]&1))u=o,u.x=la[i],u.z+=va[i],u.pa.push_back(u.x),u.v+=1ll<<u.x,Q.push(u);
}
if(A.size()<k)return puts("No"),0;sort(A.begin(),A.end(),cmp);
for(int i=0;i<A[k-1].pa.size();i++)printf("%d%c",A[k-1].pa[i],i==A[k-1].pa.size()-1?'\n':'-');
}
单源次短路
又切到一道POI，但这道题需要求单源次短路，不能用固定起点和终点的A*了
单源次短路要先求一遍最短路，然后在最短路的基础上求出目前的次短路，再对次短路进行松弛，就能得到正确答案
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5050
using namespace std;
int n,m,x,y,a,b,h,t,tot,i,ans,fir[N],C1[N],C2[N],D1[N],D2[N],n1[N],n2[N],q[N],la[N<<2],ne[N<<2],va[N<<2];bool v[N];
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;}
void w(){if(!v[y])v[q[t=t%n+1]=y]=1;}
void get(int f,int *d1,int *d2,int *nb){
for(i=2;i<=n;i++)d1[i]=d2[i]=1e9;
for(h=t=0,i=fir[1];i;w(),i=ne[i])if(va[i^f]<d1[y=la[i]])d1[y]=va[i^f],nb[y]=i;
for(;h^t;)for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])if(d1[x]+va[i^f]<d1[y=la[i]]){d1[y]=d1[x]+va[i^f];nb[y]=nb[x];w();}
for(x=2;x<=n;x++)for(i=fir[x];i;i=ne[i])if(nb[x]!=nb[la[i]]&&d1[x]+va[i^f]<d2[y=la[i]]){d2[y]=d1[x]+va[i^f];w();}
for(;h^t;)for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])if(d2[x]+va[i^f]<d2[y=la[i]]){d2[y]=d2[x]+va[i^f];w();}
}
int main(){
for(tot=1,ans=1e9,scanf("%d%d",&n,&m);m--;)scanf("%d%d%d%d",&x,&y,&a,&b),ins(x,y,a),ins(y,x,b);
get(1,D1,C1,n1);get(0,D2,C2,n2);
for(i=2;i<=n;i++)if(n1[i]!=n2[i])ans=min(ans,D1[i]+D2[i]);else ans=min(ans,min(D1[i]+C2[i],D2[i]+C1[i]));
printf("%d",ans);
}
2015年7月23日 11:48
每天二叉堆不用不知道在想些什么
2015年7月28日 11:17
尛爆oj小能手