lp4768 NOI2018 归程

克鲁斯卡尔重构树模板题。
我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点;第二个步骤,是找到这些点中到原点最小的点的距离。
我们容易发现,第一个步骤和长度无关,第二个步骤和海拔无关。
首先考虑第一个步骤。
我们建出一棵克鲁斯卡尔重构树——克鲁斯卡尔重构树是这样的一个数据结构:当你使用克鲁斯卡尔算法建最小/最大生成树的时候,每一次合并,你新建一个节点p,这个点的点权是这一次合并通过的边的边权,然后将即将合并的两个点的根节点合并到p下。这样我们构造出了一棵二叉树,其中所有叶子节点是原图上的节点。
克鲁斯卡尔重构树满足一些有意义的性质。
不妨以这题为例,我们构造一棵最大生成树,那么两点之间的lca的点权就是这两个点之间路径中边权最大的值。换句话说,从u在d的降水下可以到的节点,就是所有和u的lca的点权大于等于d的节点。考虑到这是一棵最大生成树,每个点的父亲节点的点权不会大于这个节点。这也就意味着,我们需要找到u的最高的祖先,使得这个祖先的点权大于等于d。不妨称这个祖先为w,那么w的子树的所有叶子节点,就是u在d的降水下能抵达的节点。
于是,我们求出了第一个步骤的解。
然后我们考虑第二个步骤的解。考虑到这是一张无向图,我们先求出1号节点到所有节点的距离,然后把这些值赋到叶子节点上,不妨称它为『距离权值』。因为我们每一次求min必然是求「某个点的子树中所有叶子节点的『距离权值』的最小值」,那么就可以进行树形dp,把这个最小值的信息直接记录到每个虚拟节点上。
这就做完了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=800005,M=800005;
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int a;
	int nxt;
}e[M<<1];
int h[N],et=0;
inline void Eadd(int U,int V,int W,int A){
	e[++et]=(ee){V,W,A,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int A){
	Eadd(U,V,W,A);
	Eadd(V,U,W,A);
}
struct tee{
	int v;
	int nxt;
}te[N<<1];
int g[N],tet=0;
inline void tEadd(int U,int V){
	te[++et]=(tee){V,g[U]};
	g[U]=et;
}
inline void tadd(int U,int V){
	tEadd(U,V);
	tEadd(V,U);
}
struct data{
	int u;int v;int a;
}lst[M];
inline bool cmp(const data &A,const data &B){
	return A.a>B.a;
}
int ff[N],f[N][20];
inline int fa(int X){
	return ff[X]==X?ff[X]:ff[X]=fa(ff[X]);
}
int val[N];
int n,m,cnt,rt;
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	tadd(ff[X],cnt);tadd(ff[Y],cnt);
	ff[X]=ff[Y]=cnt;
}
inline void kruskal(){
	cnt=n;
	for(int i=1;i<=m;++i){
		if(fa(lst[i].u)==fa(lst[i].v)){
			continue;
		}
		val[++cnt]=lst[i].a;
		uni(lst[i].u,lst[i].v);
		if(cnt==n*2-1){
			break;
		}
	}
	rt=fa(1);
}
int dis[N],vis[N];
struct cmp2{
	inline bool operator()(int A,int B){
		return dis[A]>dis[B];
	}
};
priority_queue< int,vector<int>,cmp2 > q;
inline void dij(){
	for(int i=2;i<=n*2;++i){
		dis[i]=INF;vis[i]=0;
	}
	vis[1]=1,dis[1]=0;
	q.push(1);
	int p;
	while(!q.empty()){
		p=q.top();q.pop();vis[p]=0; 
		for(int i=h[p];i;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].w){
				dis[e[i].v]=dis[p]+e[i].w;
				if(!vis[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
}
inline void dfs0(int X){
	for(int i=g[X];i;i=te[i].nxt){
		if(te[i].v==f[X][0]){
			continue;
		}
//		printf("%d %d\n",X,te[i].v);
		f[te[i].v][0]=X;
		for(int j=1;j<=18;++j){
			f[te[i].v][j]=f[f[te[i].v][j-1]][j-1];
		}
		dfs0(te[i].v);
		dis[X]=Min(dis[X],dis[te[i].v]);
	}
}
inline int qry(int X,int D){
	for(int i=18;i>=0;--i){
		if(val[f[X][i]]>D){
			X=f[X][i];
		}
	}
	return dis[X];
}
void init(){
	scanf("%d%d",&n,&m);
	et=tet=0;
	for(int i=1;i<=n*2;++i){
		g[i]=h[i]=0;
	}
	int u,v,w,a;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&u,&v,&w,&a);
		add(u,v,w,a);
		lst[i]=(data){u,v,a};
	}
	std::sort(lst+1,lst+1+m,cmp);
	for(int i=1;i<=n*2;++i){
		ff[i]=i;val[i]=INF;
	}
	kruskal();
	dij();
	dfs0(rt);
//	for(int i=1;i<=rt;++i){
//		printf("%d ",dis[i]);
//	}
//	puts("");
	int Q,K,S,lans=0,x,d;
	scanf("%d%d%d",&Q,&K,&S);
	for(int i=1;i<=Q;++i){
		scanf("%d%d",&x,&d);
		x=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);
		printf("%d\n",lans=qry(x,d));
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp2387 NOI2014 魔法森林

这一题据说是LCT维护边权的题目。但是我们观察一下感觉可以用动态加边SPFA来跑这道题。 具体来说,对于每一条加进来的边,我们知道,并不是整张图都因为这条边而改变。这条边会改变的有且仅有图的一部分。 因此,我们不妨将所有边按照a的大小排序,然后将b节点作为关键字,跑动态加边SPFA。 然后答案对dis[n]+e[i].a去min即可。这是因为如果它没有影响原来的最短路,那么选择这条边的a肯定不会更优;如果更新了,那么就必须要选择这条边的a。 复杂度大概是松松松,构造了菊花套菊花也没有卡掉,就假装能过吧…求大佬证明。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
const int N=50005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
struct data{
	int u;int v;int a;int b;
	inline bool operator<(const data &B){
		return a^B.a?a<B.a:b<B.b;
	}
}ed[100005];
int h[N],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W),Eadd(V,U,W);
}
int dis[N];
bool vis[N];
queue<int> q;
inline void SPFA(int s1,int s2){
	vis[s1]=vis[s2]=1;
	q.push(s1),q.push(s2);
	int p;
	while(!q.empty()){
		p=q.front();q.pop();
		for(int i=h[p];i;i=e[i].nxt){
			if(Max(dis[p],e[i].w)<dis[e[i].v]){
				dis[e[i].v]=Max(dis[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
		vis[p]=0;
	}
}
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;++i){
		dis[i]=INF;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&ed[i].u,&ed[i].v,&ed[i].a,&ed[i].b);
	}
	sort(ed+1,ed+1+m);
	int ans=INF;
	for(int i=1;i<=m;++i){
		add(ed[i].u,ed[i].v,ed[i].b);
		SPFA(ed[i].u,ed[i].v);
		ans=Min(ans,dis[n]+ed[i].a);
	}
	printf("%d\n",ans<INF?ans:-1);
}
int main(){
	init();
	return 0;
}

lp3959 NOIP2017 宝藏

我们首先,如果两个点之间有连多条边,肯定只有最短的那条最优。
那么我们进行状压,对于某一个状态\(S_{0}\),我们维护它的所有拓展的集合\(T_{S_{1}}\)
然后,记\(f_{i,k}\)表示,当前状态为\(i\),当前的深度为\(k\)时的最小花费。
这样拓展,每一次拓展都相当于把深度加深了一层,因此就可以不要花费太多的精力去考虑\(k\)对贡献的影响。
而,从某一个根开始拓展,即相当于\(f_{(1<<i),0}\)
于是我们便可以开始DP。每一次拓展都会将可行集合纳入范围。这样拓展的花费也是可以被轻松计算出来的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,m,f[1<<12][12],usf[1<<12];
int mp[15][15];
void init(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    memset(mp,0x3f,sizeof(mp));
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        --u,--v; 
        mp[u][v]=Min(mp[u][v],w);
        mp[v][u]=Min(mp[v][u],w);
    }
    const int MAX=1<<n;
    for(int i=1;i<MAX;++i){
        for(int j=0;j<n;++j){
            if((i|(1<<j))!=i){
                continue;
            }
            for(int k=0;k<n;++k){
                if(mp[j][k]!=0x3f3f3f3f){
                    usf[i]|=(1<<k);
                }
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;++i){
        mp[i][i]=0;
        f[1<<i][0]=0;
    }
    long long sm,nw,x;
    for(int i=2;i<MAX;++i){
        for(int j=i-1;j;j=(j-1)&i){
            if(((usf[i]|j)!=usf[i])){
                continue;
            }
            sm=0,nw=i^j;
            for(int k=0;k<n;++k){
                if((nw>>k)&1){
                    x=0x3f3f3f3f;
                    for(int l=0;l<n;++l){
                        if((j>>l)&1){
                            x=Min(x,mp[l][k]);
                        }
                    }
                    sm+=x;
                }
            }
            for(int k=1;k<n;++k){
                f[i][k]=Min(f[i][k],f[j][k-1]+sm*k);
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;++i){
        ans=Min(ans,f[MAX-1][i]);
    }
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}

 

lp3953 NOIP2017 逛公园

容易知道,对于每个点,最多只能偏移50。
由此可以跑记忆化搜索:\(f_{i,j}\)表示,在第i个点,比最短路长了j时的方案数。
那么,我们倒着搜即可。
具体来说,定义\(dn_{x}\)表示\(x->u\)的最短路。
那么我们可以得到状态转移方程:
$$f_{u,k}=\sum_{v,v\in S,st: \forall x \in S,x_{u}=u}f_{v,k-dn_{v}+dn_{u}-w}$$
答案为\(f_{1,K}\)
几个细节:
e[i].nxt不应写作e[i].v
不要使用长得差不多的变量。

#include<iostream>
#include<cstdio>
#include<queue> 
#include<cstring>
using namespace std;
struct ee{
    int v;
    int w;
    int nxt;
}e[400005];
int h[100005],h2[100005],et=0,n,m,K,p,dis[100005],dn[100005],f[100005][51];
bool usd[100005][51];
inline void add(int *_H,const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,_H[u]};
    _H[u]=et;
}
struct cmp2{
    inline bool operator ()(const int &X,const int &Y)const{
        return dn[X]>dn[Y];
    }
};
void dij2(){
    priority_queue< int,vector<int>,cmp2 > q;
    memset(dn,0x3f,sizeof(dn));
    dn[n]=0;
    q.push(n);
    int nw;
    while(!q.empty()){
        nw=q.top();
        q.pop();
        for(int i=h2[nw];i;i=e[i].nxt){
            if(dn[e[i].v]>dn[nw]+e[i].w){
                dn[e[i].v]=dn[nw]+e[i].w;
                q.push(e[i].v);
            }
        }
    }
}
int dfs(int u,int k){
    if(usd[u][k]){
        return -1;
    }
    if(f[u][k]){
        return f[u][k];
    }
    usd[u][k]=1;
    if(u==n){
        f[u][k]=1;
    }
    int X,sm;
    for(int i=h[u];i;i=e[i].nxt){
        //e[i].v不能写成e[i].nxt 
        sm=dn[e[i].v]-dn[u]+e[i].w;
        if(sm>k){
            continue;
        }
        X=dfs(e[i].v,k-sm);
        if(X==-1){
            return f[u][k]=-1;
        }
        f[u][k]+=X;
        f[u][k]%=p;
    }
    usd[u][k]=0;
    return f[u][k];
}
void init(){
    memset(h,0,sizeof(h));
    memset(h2,0,sizeof(h2));
    scanf("%d%d%d%d",&n,&m,&K,&p);
    et=0;
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(h,u,v,w);
        add(h2,v,u,w);
    }
    dij2();
    memset(f,0,sizeof(f));
    memset(usd,0,sizeof(usd));
    printf("%d\n",dfs(1,K));
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp4568 JLOI2011 飞行路线

首先看到点数,就考虑拆点。
把每一个点拆成k个点,分别表示已经吃了k次免费午餐的距离。
然后大力跑堆优化dij即可。可以用pair加伪函数套STL。
特别要注意是小根堆。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B)) 

struct ee{
    int v;int w;int nxt;
}e[100005];
int h[10005],et=0,f[10005][12],n,m,k,s,t;
inline void add(const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,h[u]};
    h[u]=et;
}
typedef pair<int,int> pii;
struct cmp{
	bool operator ()(const pii &A,const pii &B){
		return f[A.first][A.second]>f[B.first][B.second];
	}
};
priority_queue<pii,vector<pii>,cmp> q;
void bfs(int s){
    pii p(s,0);
    q.push(p);
    while(!q.empty()){
        p=q.top();
        q.pop();
        for(int i=h[p.first];i;i=e[i].nxt){
            if(f[e[i].v][p.second]>f[p.first][p.second]+e[i].w){
                f[e[i].v][p.second]=f[p.first][p.second]+e[i].w;
                q.push((pii){e[i].v,p.second});
            }
            if(p.second+1<=k){
                if(f[e[i].v][p.second+1]>f[p.first][p.second]){
                    f[e[i].v][p.second+1]=f[p.first][p.second];
                    q.push((pii){e[i].v,p.second+1});
                }
            }
        }
    }
}
void init(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&s,&t);
    memset(f,0x3f,sizeof(f));
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        if(u==v){
            continue;
        }
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=0;i<=k;++i){
        f[s][i]=0;
    }
    bfs(s);
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;++i){
        ans=Min(ans,f[t][i]);
    }
    printf("%d",ans);
    
}
int main(){
    init();
    return 0;
}