#include<iostream>#include<cstring>usingnamespace std;constint N =500+10;int n, m;// 这道题边的条数接近于顶点数量的²,边多是稠密图,用邻接矩阵g来存图; 如果一个图有n个节点,那么邻接矩阵的大小就是n*nint g[N][N];// d[i]代表源点s到i号点的最短路径; 比如d[4]=3代表源点到点4的最短路径为3// inf代表int值的无穷大int d[N], inf =0x3f3f3f3f;// vis数组标识某个点是否出圈; vis[4]=0代表节点4没有出圈int vis[N];// 传入源点s,计算出各个点到源点s的最短路径intdijkstra(int s){// 先将源点到所有点(包括0点)的距离初始化为无穷大inffor(int i =0; i <= n; i ++) d[i]= inf;// 修改源点到源点的最短路径, 为0d[s]=0;for(int i =1; i < n; i ++){int u =0;// u保存圈内离源点最近的点for(int j =1; j <= n; j ++)if(!vis[j]&& d[j]< d[u]) u = j;// 将找到的最近的点u出圈vis[u]=1;// 更新源点到出圈的点u的邻接点的最短路径for(int j =1; j <= n; j ++){// g[u][j]的值不等于inf代表j是u的邻接点; d[j]代表源点s到点j到的最短路径; d[u]+g[u][j]代表通过u这个点到达点j的路径长度// 对比一下点j是原先的路径更短还是通过点u到达点j是路径更短, 更新源点到点j的最短路径if(g[u][j]!= inf) d[j]=min(d[j], d[u]+ g[u][j]);}}// 如果源点1到点n的最短路径为无穷大, 说明不存在最短路径if(d[n]== inf)return-1;// 如果最短路径不是无穷大, 说明存在最短路径return d[n];}intmain(){cin >> n >> m;// 将邻接矩阵每条边的权重都初始化为无穷大memset(g,0x3f,sizeof g);// 使用邻接矩阵存储图; 若某个点到某个点有边,那么就在对应位置上存上权重,且始终存最小权重for(int i =0; i < m; i ++){int a, b, w;cin >> a >> b >> w;g[a][b]=min(g[a][b], w);}// 因为这道题要算点1到点n的最短路径, 那么源点就可以设置成1, 通过dijkstra算法可以得到源点1到所有点的最短路径, 并在算法的最后返回源点1到点n的最短路径cout <<dijkstra(1)<< endl;return0;}
(2)堆优化版的Dijkstra算法——适用于稀疏图
#include<iostream>#include<cstring>#include<queue>usingnamespace std;constint N =2e5+10;typedef pair<int,int> PII;// 优先级队列q相当于大根堆// 这里堆顶放的是距离源点最近的点,比如该点距离源点的距离为3,其他点距离源点的距离更大,取相反数后插入堆中,那么距离最近的就是值最大的,放在堆顶// 堆q每个元素为一个对组,键为源点到该点的最短路径,值是点
priority_queue<PII> q;// vis标记某点是否已出队,只有未出队的才能更新它的邻接点的最短路径; vis[2]=0代表2这个点未出队// d[i]代表源点到点i的最短路径int vis[N], d[N], inf =0x3f3f3f3f;// 这道题边比较少,是稀疏图,用邻接表存图; w数组存储权重int h[N], e[N], ne[N], w[N], idx;int n, m;voidadd(int a,int b,int c){e[idx]= b, ne[idx]= h[a], w[idx]= c, h[a]= idx ++;}intdijkstra(int s){// 将源点到所有点的最短路径初始化为无穷大for(int i =0; i <= n; i ++) d[i]= inf;// 将源点加入堆d[s]=0; q.push({-d[s], s});while(q.size()){// 取堆顶; 取出距离源点最近的点auto t = q.top(); q.pop();int u = t.second;// 如果已经出队过,就不能更新邻接点if(vis[u])continue;// 如果没有出队过,标记它现在已经出队过vis[u]=1;// 更新该点的邻接点的最短路径for(int i = h[u]; i !=-1; i = ne[i]){int j = e[i], c = w[i];// 如果邻接点需要更新,则加入堆中if(d[u]+ c < d[j]){d[j]= d[u]+ c;q.push({-d[j], j});}}}if(d[n]== inf)return-1;return d[n];}intmain(){cin >> n >> m;memset(h,-1,sizeof h);for(int i =0; i < m; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout <<dijkstra(1)<< endl;return0;}
4. SPFA算法——求源点到其他所有点的最短路径、判断是否存在负环(可以处理负边权)
(1)求有负边权的图的最短路径——求源点到其他所有点的最短路径
#include<iostream>#include<cstring>#include<queue>usingnamespace std;constint N =1e5+10;int h[N], e[N], ne[N], w[N], idx;
queue<int> q;int d[N], inf =0x3f3f3f3f;// vis[i]代表点i是否在队中; vis[3]=1代表点3在队中, vis[3]=0代表点3不在队中int vis[N];int n, m;voidadd(int a,int b,int c){e[idx]= b, ne[idx]= h[a], w[idx]= c, h[a]= idx ++;}voidspfa(int s){// 将源点到全部点的最短路径全部初始化为无穷大memset(d, inf,sizeof d);d[s]=0;// 将源点入队q.push(s); vis[s]=1;while(q.size()){// 出队队头,标记队头不在队中int f = q.front(); q.pop(); vis[f]=0;// 更新队头邻接点的最短路径for(int i = h[f]; i !=-1; i = ne[i]){int j = e[i], c = w[i];if(d[f]+ c < d[j]){d[j]= d[f]+ c;// 如果点j不在队中,则加入队中if(!vis[j]) q.push(j), vis[j]=1;}}}if(d[n]== inf) cout <<"impossible"<< endl;else cout << d[n]<< endl;}intmain(){cin >> n >> m;memset(h,-1,sizeof h);for(int i =0; i < m; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c);}spfa(1);return0;}
(2)判断图中是否存在负环(负环指环的权重和为负数)
#include<iostream>#include<cstring>#include<queue>usingnamespace std;constint N =1e5+10;int n, m;int h[N], e[N], ne[N], w[N], idx;
queue<int> q;// 在图上增加一个虚拟源点,虚拟源点到图中每个点都有条权重为0的边// cnt数组代表虚拟源点到该点的最短路径的边数; 比如cnt[3]=3代表虚拟源点到点3的最短路径的边数为3int d[N], vis[N], cnt[N];voidadd(int a,int b,int c){e[idx]= b, ne[idx]= h[a], w[idx]= c, h[a]= idx ++;}boolspfa(){// 把所有点加入队列中for(int i =1; i <= n; i ++) q.push(i), vis[i]=true;while(q.size()){int f = q.front(); q.pop(); vis[f]=0;for(int i = h[f]; i !=-1; i = ne[i]){int j = e[i], c = w[i];// 更新源点到点j的最短路径if(d[f]+ c < d[j]){// 更新最短路径的长度d[j]= d[f]+ c;// 更新最短路径的边数cnt[j]= cnt[f]+1;// 如果虚拟源点到点j的边数大于等于节点数,则存在负环if(cnt[j]>= n)returntrue;if(!vis[j]) q.push(j), vis[j]=1;}}}// 图中不存在负环returnfalse;}intmain(){cin >> n >> m;memset(h,-1,sizeof h);for(int i =0; i < m; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout <<(spfa()?"Yes":"No")<< endl;return0;}
5. Floyd算法——求图中任意两点之间的最短路径(可以处理负边权)
#include<iostream>usingnamespace std;constint N =200+10;// d[i][j]代表点i到点j经过节点1~k的最短路径的长度; 例如d[1][3]=2代表点1到点3的最短路径长度为2int d[N][N], INF =0x3f3f3f3f;int n, m, k;// 更新两点之间的最短路径voidfloyd(){for(int k =1; k <= n; k ++)for(int i =1; i <= n; i ++)for(int j =1; j <= n; j ++)d[i][j]=min(d[i][j], d[i][k]+ d[k][j]);}intmain(){cin >> n >> m >> k;// 处理自环; 图中有可能存在自环,比如点1到点1存在条边,那么点1到点1的最短路径就是0for(int i =1; i <= n; i ++){for(int j =1; j <= n; j ++){if(i == j) d[i][j]=0;else d[i][j]= INF;}}// d可以先看成一个邻接矩阵,存储两点之间边的最小权重for(int i =0; i < m; i ++){int a, b, w;cin >> a >> b >> w;// 图中两点之间可能有重边,保留权重最小的那条边即可d[a][b]=min(d[a][b], w);}floyd();while(k --){int a, b;cin >> a >> b;// 如果点a到点b的距离不是无穷大,则存在最短路径; 是无穷大,不存在最短路径; // 这里将无穷大定义为INF/2是因为,就算点a到点b不存在最短路径,但由于存在负边权,有可能使得路径从无穷大变得比无穷大小一些// 所以如果当前点a到点b的路径比无穷大的一半还大,我们就认为两点之间还是无穷大,还是没有最短路径if(d[a][b]> INF /2) cout <<"impossible"<< endl;else cout << d[a][b]<< endl;}return0;}
有一些几句话就可以说明白的观点或者解决的的问题,小虎单独收集到这里。
Commits没有算入每天的activity
fork的仓库是不算的。 Commits made in a fork will not count toward your contributions. 参考: Contribution activity not shown for github…
直接使用vtkConnectivityFilter提取连通区域,渲染上没问题,但是打印出polydata中的点数,发现跟原始数据是一致的。 for (int i 0; i < numRegions; i){vtkSmartPointer<vtkConnectivityFilter> connectivityFilter vtkSmartPointe…