问题描述
【题目描述】
【输入】
【输出】
【样例输入】
7 10 4
1 3 10
2 6 9
4 1 5
3 7 4
3 6 9
1 5 8
2 7 4
3 2 10
1 7 6
7 6 9
1 7 1 0
1 7 3 1
2 5 1 0
3 7 2 1
【样例输出】
9
6
8
8
题目解析
最小生成树简单算法
对于每一次问询，关注若干点后，我们需要按照最小生成树的方法生成n-1条边，此时关注点全部连通，然后求出其中的最大边就是答案。
倍增法优化最小生成树
新思路
- 首先生成最小生成树 M S T MST MST；
- 对每一次问询都要将关注点放入 M S T MST MST；
- 维护 m a x c o s t max{cost} maxcost；
在维护 m a x c o s t max{cost} maxcost用到倍增法求最近公共祖先lca，倍增法就是要用额外的数据来存放每一个点。 f f [ i ] [ j ] ff[i][j] ff[i][j]表示点i向上移动 2 i 2^i 2i次到达节点的标号。
倍增法LCA
- 对 f f [ ] [ ] ff[][] ff[][]数组进行预处理，用到了 d f s dfs dfs算法；
- 求 l c a lca lca，将 a a a和 b b b调到同一个高度；
- 在2的过程中维护 m a x max max、 s u m sum sum、 a v g avg avg、 m i n min min。
C++代码
最小生成树简单算法
#include<bits/stdc++.h>
using namespace std;
int N,M,Q;
const int MaxM = 2*10^5;
const int MaxN = 50001;
struct Edge //边的抽象
{
int from,to,cost; //起点终点代价
Edge(int from,int to,int cost)
{
this->from = from;
this->to = to;
this->cost = cost;
}
};
bool cmp(Edge *e1,Edge *e2)
{
return e1->cost<e2->cost;
}
Edge *edges[MaxM];
//并查集
struct UFNode
{
UFNode *parent;
UFNode():parent(NULL){
}
};
UFNode *find(UFNode *p)
{
if(p->parent==NULL) return p;
set<UFNode*> path;
while(p->parent!=NULL)
{
path.insert(p);
p = p->parent;
}
set<UFNode *>::iterator iter = path.begin();
while(iter!=path.end())
{
(*iter)->parent=p;
iter++; //指针后移
}
return p;
}
void merge(UFNode *p1,UFNode *p2) //并查集合并
{
find(p2)->parent = find(p1);
}
UFNode ufnodes[MaxN]; //并查集的节点，一开始各自独立
void easy(int l,int r,int mod,int c)
{
for(int j=0;j<=N;j++) ufnodes[j].parent = NULL; //重新初始化NULL
//逐步加入边到最小生成树中
for(int i=0;i<M;i++)
{
Edge *pEdge = edges[i];
int from = pEdge->from;
int to = pEdge->to;
int cost = pEdge->cost;
if(find(&ufnodes[from])==find(&ufnodes[to])) continue; //如果这两个点已经在一棵树上就不采纳
else merge(&ufnodes[from],&ufnodes[to]); //并查集合并
UFNode * parent = NULL;
bool isOk = true;
for(int i=l;i<=r;i++)
{
if(i%mod==c) //i值关注点的编号
{
if(parent==NULL) parent = find(&ufnodes[i]); //第一个关注点的老大
else if(parent!=find(&ufnodes[i])) //没有联通
{
isOk = false;
break;
}
}
}
if(isOk) //关注点都联通了
{
printf("%d\n",cost);
break;
}
}
}
int main()
{
scanf("%d %d %d",&N,&M,&Q);
for(int i=0;i<M;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
Edge *e = new Edge(a,b,c);
edges[i] = e;
}
sort(edges,edges+M,cmp); //排序
for(int i=0;i<Q;i++)
{
int l,r,mod,c;
scanf("%d %d %d %d",&l,&r,&mod,&c);
easy(l,r,mod,c);
}
return 0;
}
倍增法优化最小生成树代码
#include<bits/stdc++.h>
using namespace std;
int N,M,Q;
const int MaxM = 2*10^5;
const int MaxN = 50001;
int ff[MaxN][17]; //ff[i][j]表示标号为i的节点往根节点的方向移动2^i次达到的节点编号
int mm[MaxN][17]; //mm[i][j]指的是标号为i的节点往根节点的方向移动2^i次过程中的最大权
int depth[MaxN]; //记录每个点在mst中的深度
int vis[MaxN]; //记录耨个是否被访问过
struct Edge //边的抽象
{
int from,to,cost; //起点终点代价
Edge(int from,int to,int cost)
{
this->from = from;
this->to = to;
this->cost = cost;
}
};
bool cmp(Edge *e1,Edge *e2)
{
return e1->cost<e2->cost;
}
Edge *edges[MaxM];
//并查集
struct UFNode
{
UFNode *parent;
UFNode():parent(NULL){
}
};
UFNode *find(UFNode *p)
{
if(p->parent==NULL) return p;
set<UFNode*> path;
while(p->parent!=NULL)
{
path.insert(p);
p = p->parent;
}
set<UFNode *>::iterator iter = path.begin();
while(iter!=path.end())
{
(*iter)->parent=p;
iter++; //指针后移
}
return p;
}
void merge(UFNode *p1,UFNode *p2) //并查集合并
{
find(p2)->parent = find(p1);
}
UFNode ufnodes[MaxN]; //并查集的节点，一开始各自独立
int maxUsingLca(int a,int b) //倍增法求lca顺便求max权重
{
int ans = -1;
if(depth[a]<depth[b]) //将a的深度调到更深
{
int t=a;
a=b;
b=t;
}
int k=depth[a]-depth[b]; //将a调到和b同一高度
for(int i=0;(1<<i)<=k;i++)
{
if((1<<i)&k)
{
ans = max(ans,mm[a][i]);
a = ff[a][i];
}
}
//至此a和b已经在同一层上
for(int j=16;j>=0;j--)
{
if(ff[a][j]==ff[b][j]) continue;
else
{
ans = max(ans,mm[a][j]);
ans = max(ans,mm[b][j]);
a = ff[a][j];
b = ff[b][j];
break;
}
}
ans = max(ans,mm[a][0]);
ans = max(ans,mm[b][0]); //再往上走一步就得到了lca
return ans;
}
void mid(int l,int r,int mod,int c)
{
int ans = -1;
int left = l-l%mod+c;
if(left<l) left += mod;
for(;left+mod<=r;left+=mod)
{
ans = max(ans,maxUsingLca(left,left+mod));
}
printf("%d\n",ans);
}
//最小树的生成及表示
vector<Edge *> mst[MaxN];
void buildMST()
{
int cnt = 0; //已加入边的数量
//逐步加入边到最小生成树中
for(int i=0;i<M;i++)
{
Edge *pEdge = edges[i];
int from = pEdge->from;
int to = pEdge->to;
int cost = pEdge->cost;
if(find(&ufnodes[from])==find(&ufnodes[to])) continue; //如果这两个点已经在一棵树上就不采纳
else
{
merge(&ufnodes[from],&ufnodes[to]); //并查集合并
cnt++;
mst[from].push_back(pEdge);
Edge *other = new Edge(to,from,cost);
mst[to].push_back(other);
if(cnt==N-1) //构建完成
{
break;
}
}
}
}
void dfs(int start,int parent,int d) //start表示开始点编号，parent表示父结点编号，d表示这个点的深度
{
depth[start] = d+1;
vis[start] = 1;
//向上走
for(int i=1;i<17;i++)
{
ff[start][i] = ff[ff[start][i-1]][i-1];
mm[start][i] = max(mm[start][i-1],mm[ff[start][i-1]][i-1]);
}
//向下递归找到所有儿子
for(int i=0;i<mst[start].size();i++)
{
Edge *child = mst[start][i]; //儿子
if(vis[child->to]) continue;
ff[child->to][0] = start;
mm[child->to][0] = child->cost;
dfs(child->to,start,d+1);
}
}
void preLca()
{
ff[1][0] = 1; //定义1号节点为树的根节点
mm[1][0] = 0; //定义1号节点为根节点
dfs(1,1,0);
}
int main()
{
scanf("%d %d %d",&N,&M,&Q);
for(int i=0;i<M;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
Edge *e = new Edge(a,b,c);
edges[i] = e;
}
sort(edges,edges+M,cmp); //排序
buildMST(); //生成最小树
preLca(); //为倍增法做预处理
for(int i=0;i<Q;i++)
{
int l,r,mod,c;
scanf("%d %d %d %d",&l,&r,&mod,&c);
mid(l,r,mod,c);
}
return 0;
}
转载：https://blog.csdn.net/SAMSARS/article/details/116132725
查看评论