宠物托运网站开发,宝安网站改版,百度网站诊断,房产交易网站建设策划案目录
迪杰斯特拉模板#xff08;用来求一个点出发到其它点的最短距离#xff09;#xff1a;
克鲁斯卡尔模板#xff08;用来求最小生成树#xff09;#xff1a;
题目一#xff08;蓝桥王国#xff09;#xff1a;
题目二#xff08;随机数据下的最短路径#…目录
迪杰斯特拉模板用来求一个点出发到其它点的最短距离
克鲁斯卡尔模板用来求最小生成树
题目一蓝桥王国
题目二随机数据下的最短路径
题目三出差
题目四聪明的猴子 题目六机房
迪杰斯特拉模板用来求一个点出发到其它点的最短距离
#includeiostream
#includequeue
#includevector
#includecstring
using namespace std;
typedef long long ll;
const ll N 3e5 10, M 1e6 10, inf 1e14;
struct node
{ll v, w;bool operator (const node y) const//重载一个,用于优先队列排序{return w y.w;//小到大}
};
int n, m;
priority_queuenodeq;
vectornode e[N];
ll dis[N], vis[N];
void Dij()
{dis[1] 0;//从1号点出发表示从1到1距离为0q.push({ 1,dis[1] });//1号点以及到1的距离入队while (q.size()){int u q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v i.v, w i.w;//取其相连的点及权值if (dis[v] dis[u] w)//经过u点到v点的权值小于之前的权值则更新{dis[v] dis[u] w;q.push({ v,dis[v] });//v点以及到v的距离}}}}
int main()
{cin n m;fill(dis1, dis1n, inf);//赋值一个无穷大表示没有连接for (int i 1; i m; i){int x, y, w;cin x y w;e[x].push_back({ y,w });//存入以x出发到y权值为w}Dij();
}
克鲁斯卡尔模板用来求最小生成树
#includeiostream
#includevector
#includealgorithm
#includecmath
using namespace std;
const int N 1e320;
int m, n;
int h[N],f[N],x[N],y[N];
struct edge
{int v1, v2;double w;
};
vectoredge e;
int find(int k)//查找
{if (f[k] k)return k;return f[k] find(f[k]);
}
void merge(int x, int y)//合并
{xfind(x),yfind(y);if (x! y)f[x] f[y];
}
bool cmp(edge a, edge b)
{return a.w b.w;
}
int main()
{cin n;for (int j 1; j n; j){cin x[j] y[j] h[j];f[j] j;//初始化并查集根}cinm;for (int j 1; j m; j)//添加边{int v1,v2,w;cinv1v2w;e.push_back({ v1, v2, w });}sort(e.begin(), e.end(), cmp);//边从小到大排序int cnt0;for (int i 0; i e.size(); i){if (find(e[i].v1) ! find(e[i].v2))//不属于一个集合{merge(e[i].v1, e[i].v2);//合并}if (cnt n-1)//n个点只需要n-1条边选取n-1条边后跳出循环break;}
}
题目一蓝桥王国 #includeiostream
#includequeue
#includevector
#includecstring
using namespace std;
typedef long long ll;
const ll N 3e5 10, M 1e6 10, inf 1e14;
struct node
{ll v, w;bool operator (const node y) const//重载一个,用于优先队列排序{return w y.w;//小到大}
};
int n, m;
priority_queuenodeq;
vectornode e[N];
ll dis[N], vis[N];
void Dij()
{dis[1] 0;//从1号点出发表示从1到1距离为0q.push({ 1,dis[1] });//1号点以及到1的距离入队while (q.size()){int u q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v i.v, w i.w;//取其相连的点及权值if (dis[v] dis[u] w)//经过u点到v点的权值小于之前的权值则更新{dis[v] dis[u] w;q.push({ v,dis[v] });//v点以及到v的距离}}}}
int main()
{cin n m;fill(dis1, dis1n, inf);//赋值一个无穷大表示没有连接for (int i 1; i m; i){int x, y, w;cin x y w;e[x].push_back({ y,w });//存入以x出发到y权值为w}Dij();for (int i 1; i n; i){if (dis[i] inf)//无法到达cout -1 ;elsecout dis[i] ;}
}
题目二随机数据下的最短路径 #includeiostream
#includequeue
#includevector
#includecstring
using namespace std;
typedef long long ll;
const ll N 3e5 10, M 1e6 10, inf 1e14;
struct node
{ll v, w;bool operator (const node y) const//重载一个,用于优先队列排序{return w y.w;//小到大}
};
int n, m, t;
priority_queuenodeq;
vectornode e[N];
ll dis[N], vis[N];
void Dij(int t)
{dis[t] 0;//从t号点出发表示从t到t距离为0q.push({ t,dis[t] });//t号点以及到t的距离入队while (q.size()){int u q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v i.v, w i.w;//取其相连的点及权值if (dis[v] dis[u] w)//经过u点到v点的权值小于之前的权值则更新{dis[v] dis[u] w;q.push({ v,dis[v] });//v点以及到v的距离}}}}
int main()
{cin n m t;fill(dis1, dis1n, inf);//赋值一个无穷大表示没有连接for (int i 1; i m; i){int x, y, w;cin x y w;e[x].push_back({ y,w });//存入以x出发到y权值为w}Dij(t);//从t点出发for (int i 1; i n; i){if (dis[i] inf)//无法到达cout -1 ;elsecout dis[i] ;}
}
题目三出差 #includeiostream
#includequeue
#includevector
#includecstring
using namespace std;
typedef long long ll;
const ll N 3e5 10, M 1e6 10, inf 1e14;
struct node
{int v, w;bool operator (const node y) const//重载一个,用于优先队列排序{return w y.w;//小到大}
};
int n, m;
priority_queuenodeq;
vectornode e[N];
int dis[N], vis[N], time0[N];
void Dij()
{dis[1] 0;//从1号点出发表示从1到1距离为0q.push({ 1,dis[1] });//1号点以及到1的距离入队while (q.size()){int u q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v i.v, w i.w;//取其相连的点及权值if (dis[v] dis[u] w)//经过u点到v点的权值小于之前的权值则更新{dis[v] dis[u] w;q.push({ v,dis[v] });//v点以及到v的距离}}}
}
int main()
{cin n m;for (int i 1; i n; i)cin time0[i];fill(dis 1, dis 1 n, inf);//赋值一个无穷大表示没有连接for (int i 1; i m; i){int x, y, w;cin x y w;e[x].push_back({ y,w time0[y]});//存入以x出发到y权值为w隔离时间e[y].push_back({ x,w time0[x] });//存入以y出发到y,权值为w隔离时间}Dij();cout dis[n] - time0[n];//要减掉最后终点的隔离时间
}
题目四聪明的猴子 #includeiostream
#includevector
#includealgorithm
#includecmath
using namespace std;
const int N 1e320;
int m, n;
int a[N],f[N],x[N],y[N];
struct edge
{int v1, v2;double w;
};
vectoredge e;
int find(int k)//查找
{if (f[k] k)return k;return f[k] find(f[k]);
}
void merge(int x, int y)//合并
{xfind(x),yfind(y);if (x! y)f[x] f[y];
}
bool cmp(edge a, edge b)
{return a.w b.w;
}
int main()
{cin m;for (int i 1; i m; i)cin a[i];cin n;for (int j 1; j n; j){cin x[j] y[j];f[j] j;//初始化并查集根}for(int i1;in;i)for (int j i 1; j n; j)//添加边{double w sqrt((x[i] - x[j]) * (x[i] - x[j]) (y[i] - y[j]) * (y[i] - y[j]));e.push_back({ i, j, w });}sort(e.begin(), e.end(), cmp);//边从小到大排序double maxw 0.0;//记录最小生成树中最大边int cnt 0;for (int i 0; i e.size(); i){if (find(e[i].v1) ! find(e[i].v2))//不属于一个集合{merge(e[i].v1, e[i].v2);//合并cnt;maxw max(maxw, e[i].w);//更新最小生成树中最大边}if (cnt n-1)//n个点只需要n-1条边选取n-1条边后跳出循环break;}int ans 0;for (int i 1; i m; i){if (a[i] maxw)//有几只猴子大于最小生成树中最大边ans;}cout ans;
}
题目五通电 #includeiostream
#includevector
#includealgorithm
#includecmath
using namespace std;
const int N 1e320;
int m, n;
int h[N],f[N],x[N],y[N];
struct edge
{int v1, v2;double w;
};
vectoredge e;
int find(int k)//查找
{if (f[k] k)return k;return f[k] find(f[k]);
}
void merge(int x, int y)//合并
{xfind(x),yfind(y);if (x! y)f[x] f[y];
}
bool cmp(edge a, edge b)
{return a.w b.w;
}
int main()
{cin n;for (int j 1; j n; j){cin x[j] y[j] h[j];f[j] j;//初始化并查集根}for(int i1;in;i)for (int j i 1; j n; j)//添加边{double w sqrt((x[i] - x[j]) * (x[i] - x[j]) (y[i] - y[j]) * (y[i] - y[j]))(h[i]-h[j])*(h[i]-h[j]);e.push_back({ i, j, w });}sort(e.begin(), e.end(), cmp);//边从小到大排序double maxw 0.0;//记录最小生成树中最大边double ans0;int cnt0;for (int i 0; i e.size(); i){if (find(e[i].v1) ! find(e[i].v2))//不属于一个集合{merge(e[i].v1, e[i].v2);//合并anse[i].w;//求和maxw max(maxw, e[i].w);//更新最小生成树中最大边}if (cnt n-1)//n个点只需要n-1条边选取n-1条边后跳出循环break;}printf(%.2lf,ans);
} 题目六机房 #includeiostream
#includequeue
#includevector
#includecstring
using namespace std;
typedef long long ll;
const ll N 3e5 10, M 1e6 10;
struct node
{ll v, w;bool operator (const node y) const//重载一个,用于优先队列排序{return w y.w;//小到大}
};
int n, m;
priority_queuenodeq;
vectornode e[N];
vectornode temp;
ll dis[N], vis[N], cnt[N];
ll Dij(int u, int end)
{memset(vis, 0, sizeof(vis));memset(dis, 0x3f3f, sizeof(dis));dis[u] 0;//从u号点出发表示从u到u距离为0q.push({ u,dis[u] });//u号点以及到u的距离入队while (q.size()){int u q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v i.v, w i.w;//取其相连的点及权值if (dis[v] dis[u] w)//经过u点到v点的权值小于之前的权值则更新{dis[v] dis[u] w;q.push({ v,dis[v] });//v点以及到v的距离}}}return dis[end]cnt[end];//还需要加上自身延迟
}
int main()
{cin n m;for (int i 1; i n - 1; i){int x, y;cin x y;cnt[x], cnt[y];temp.push_back({ x,y });//临时存两个顶点}for (int i 0; i n - 1; i)//根据度构造边{int u temp[i].v, v temp[i].w;e[u].push_back({ v,cnt[u] });//u-v的边权值为u的度e[v].push_back({ u,cnt[v] });}while (m--)//m次查询{int u, v;cin u v;if (u v)cout cnt[u] endl;else{ll ans Dij(u, v);cout ans endl;}}
}
