辽阳哪里做网站wordpress添加友链申请

当前位置： 首页 > news >正文

辽阳哪里做网站,wordpress添加友链申请,html5行业网站,莱阳建设局网站今天开始讲图论 目录 图的存储 算任意两点的最短路径: floyed算法#xff1a; 算一个点到其他所有点的最短距离 dijkstra算法: spfa算法#xff1a; 图的存储 其实#xff1a;邻接矩阵和链式向前星都能存边的信息#xff0c;vector只能存点的信息#xff0c;再搭配上v[]…今天开始讲图论 目录 图的存储 算任意两点的最短路径: floyed算法 算一个点到其他所有点的最短距离 dijkstra算法: spfa算法 图的存储 其实邻接矩阵和链式向前星都能存边的信息vector只能存点的信息再搭配上v[]便可存点的权值如果是树的话也建议vector 邻接矩阵可存边信息     邻接表vector法存点信息也可以搞一个fa[]存每个点父亲     链式向前星存边信息      下面是链式向前星的模板  #include bits/stdc.h using namespace std; int tot,n,m; int head[100];//存放每个点起边的标号 struct edge{int to,w,next;//to是边终点next是下一条边的标号不用存起点因为我们是通过起点来找边号的 }e[100];//存储边每条边都有唯一下标 void add(int u,int v,int w){e[tot].tov; //这里我们一般从1开始存边是因为head里面我们默认0时无边 e[tot].ww;e[tot].nexthead[u]; head[u]tot;//后来的边就插在最前面这里有个细节因为最开始head内容是0所以最后一个边的next一定是0 } int main(){int u,v,w;cinnm; //n个点,m个边for(int i1;im;i){cinuvw;add(u,v,w);}for(int x1;xn;x){//把每个起点都遍历一遍for(int ihead[x];i!0;ie[i].next){ //遍历每个点连的边icoutx,e[i].to\n;}} } 算任意两点的最短路径: floyed算法 O(n^3) 可以处理负权图不能判断负环图 思想从第一个点开始循环n次依次加入每个点看看因为这个点的加入所有点间距离因此而变小就更新 int main(){ //floyed算法int n;cinn;int w[n1][n1];memset(w,0x3f,sizeof(w));//若是无向图对角点初始化为0即可有联系的点间放权值即可对角点要初始化for(int k1;kn;k)//依次放入每个点进行中转这一层是可以单独拿出来的for(int i1;in;i)for(int j1;jn;j){if(w[i][j]w[i][k]w[k][j])//距离变短就更新w[i][j]w[i][k]w[k][j]; } }算一个点到其他所有点的最短距离 spfa算法 O(nm)O(KV) 可以处理负权图判断负环图负环就是一圈相加起来的权值是个负数          思想先将起点加入队列每次从队列中取出一个点遍历相邻边找到因该点加入而距离变小的点更新更新成功的点重新入队重复至队空       bellman-ford算法 时间复杂度O(nm)  可以处理负权图判断负环图       dijkstra算法 O(n^2)或O(nlogn)  只能处理非负权图          思想每次贪心地选出一个最小路径的点变成白点(确定点)遍历相邻边找到因该点加入而距离变小的点更新重复至队空​​​​​​​白点自动会跳过 如果出现负权这会直接导致选白点的时候就出错了因此就不能使用该算法        题  dijkstra算法: 原理贪心思想确定白点的过程就是贪心故不能处理负边权  1. 初始化dis[s]0其余点dis为无穷大. 2. 取出队中dis值最小的蓝点cur变成白点后遍历周围点v当dis[cur]wdis[v]就更新dis[v] 若cur已为白点就跳过这点不同于spfa 3被更新的点入队等待重新更新周围点 4重复操作直到队空也就是所有点都变成了白点        注意队列一些点的dis值会越来越多分两种情况(对蓝点)取出来的一定是可以变成白点的不用管; (对白点)dis中值一定比队列中的小我们跳过即可        我们提供有两种判断办法 第一种是对出队元素pos的dis和dis[cur]比较若不相等则说明选出旧白点了就跳过 第二种方法是对已经成为白点的进行标记若出队元素早已经是白点了就跳过       #include bits/stdc.h
using namespace std; typedef pairint,int pa; //pair中first是距离second是起点到的它点 const int N1e510,M2e510; int n,m,s,t,tot; int pre[N]; int head[N],dis[N],vis[N]; //head[i]存放起点i周围的边号vis标记此点是否为白点即已确定的点 struct edge {int to,w,next; } e[M];//如果NM没有const修饰这里要报错的 priority_queuepa,vectorpa,greaterpa Q; //小根堆按dis升序排列void add(int u,int v,int w) {etot{v,w,head[u]};head[u]tot;} void dijkstra(int s) {memset(dis,0x3f,sizeof(dis));dis[s]0;Q.push(make_pair(0,s)); //make_pair函数的返回值是一个pair功能是将两个数据合成一个pairwhile (!Q.empty()) {int curQ.top().second;Q.pop();//出队就相当于取出最小蓝点if (vis[cur]) continue;//跳过旧白点vis[cur]1;for (int ihead[cur];i;ie[i].next) { //i为边号 遍历cur连向周围所有边i的点vint ve[i].to,we[i].w; if (dis[cur]wdis[v]) dis[v]dis[cur]w,Q.push(make_pair(dis[v],v));//更新后就要入队等待重新更新周围点}} } int main() {cinnms;int u,v,w;for (int i1;im;i) {cinuvw;add(u,v,w);}dijkstra(s);for (int i1;in;i) coutdis[i] ;return 0; }//另一个判断方式具体路径输出 void print(int u){if(u0)return;print(pre[u]);coutu-; } void dijkstra(int s) {memset(dis,0x3f,sizeof(dis));dis[s]0;Q.push(make_pair(0,s)); while (!Q.empty()) {int posQ.top().second,disQ.top().first; Q.pop();if (dis!dis[pos]) continue;//跳过旧白点for (int ihead[pos];i;ie[i].next) { int toe[i].to,we[i].w; if (dis[pos]wdis[to]) dis[to]dis[pos]w,pre[v]cur,Q.push(make_pair(dis[to],to));}} } main:for (int i1;in;i) {coutdis[i]: ;print(i);cout\n;}spfa算法步骤 原理就是线性dp由以确定点按拓扑序推下个未确定点然后未确定点由前面多个以确定点决策就是按层递推 1. 初始化dis[s]0其余dis为无穷大vis[s]1 2cur出队遍历周围点v当dis[cur]wdis[v]就更新dis[v]vis[cur]0 3(松弛入队)被更新的且不在队伍的点入队等待重新更新周围点vis[v]1这一步与dijkstra不同,因为已经入过队的可能还会入队故可处理负边权 4重复操作直到队空        不过此题卡spfa但是因为还是要给出来因为spfa算法可用地方太多了比如spfa还可以处理最长路问题 #include bits/stdc.h using namespace std;
const int N1e4, M1e4; int head[N],vis[N],dis[N],tot,n,m;//head是表头head[i]表示i起点的边号vis表示该点是否已在队列中为了防止同个点重复入队 struct node{int to,w,next;} e[M]; void add(int u,int v,int w){etot{v,w,head[u]};head[u]tot;} void spfa(int t){queueint q;memset(dis,0x3f,sizeof(dis));dis[t]0; vis[t]1; //注意vis等于1表示队列中已经存在此点q.push(t);while(!q.empty()){int curq.front(); q.pop();vis[cur]0;//扩展后此点出队for(int ihead[cur];i;ie[i].next){//i是边号 遍历点cur连向的周围边i的点vint ve[i].to,we[i].w;if(dis[v]dis[cur]w){//判断是否需要更新更新过的且不在队伍的点才入队方便找更优解dis[v]dis[cur]w;if(!vis[v])q.push(v),vis[v]1;}}} } int main(){int n,m,t;cinnmt;for(int i1;im;i){int u,v,w;cinuvw;add(u,v,w);}spfa(t);for(int i1;in;i){coutdis[i] ;}return 0; } 题目我们把上百件衣服从商店运回赛场求最短的从上商店到赛场的路线 输入第一行N(100),M(10000),N表示有几个路口(1号路口是商场所在地n号是赛场)M表示有几条路NM0时输入结束接下来M行每行包括ABC表示AB两口路需要耗时C时间 输出对每组输入输出一行表示工作人员从商店到赛场的最短时间 样例 2 1           输出3             1 2 3                   2             3 3             1 2 5             2 3 5             3 1 2             0 0 #include bits/stdc.h
using namespace std; const int N1e410; const int M1e410; long long dis[N],u[N],v[N],w[N];//按边初始化无向图 int n,m,cnt; long long ans; long long bellman_fold(int s,int t){memset(dis,0x3f,sizeof(dis));//初始化无穷大dis[s]0;for(int i1;in-1;i){//最多松弛n-1次int check0;//是否可以提前结束松弛for(int j1;jcnt;j){//对每条边进行松弛更新disif(dis[u[j]]w[j]dis[v[j]]){dis[v[j]]dis[u[j]]w[j];check1;}}if(check0)break;}return dis[t]; } int main(){while((cinnm)(nm)){cnt1;for(int i1;im;i){//初始化无向图(按边)因为只需要用到每条边所有初始化只需要按边初始化即可int x,y,z;cinxyz;u[cnt]x;v[cnt]y;w[cnt]z;//w表示每条边的长度u表示对应边的起点v表示对边的终点这样方便对每条边访问cnt;u[cnt]y;v[cnt]x;w[cnt]z;cnt;}ansbellman_fold(1,n);coutansendl;} } 不过bellman我不怎么用只是给出来一下。