-
算法整理（五）
10.图论
10.1 最小生成树
10.1.1 Prim算法
#includeusing namespace std; #define inf 0x7fffffff int n,m,sum; int dis[5005],vis[5005]; struct Edge { int des,w; }ed1,ed2; vector<Edge>vec[5005]; int prim() { for(int i=2;i<=n;i++) dis[i]=inf;//初始化：各点到树的距离为无穷大 int now=1;//默认从1开始建树 for(int i=0;i<vec[1].size();i++) dis[vec[1][i].des]=min(vec[1][i].w,dis[vec[1][i].des]); //更新：此时树中有1个元素1，于是各点到树的距离即为到1的距离 for(int i=2;i<=n;i++) { vis[now]=1; int minn=inf; int index=0; for(int j=2;j<=n;j++) { if(dis[j]<minn&&!vis[j]) { minn=dis[j]; index=j; } }//遍历未被访问的各点，找到距离树最近的点 if(!index) return -1;//如果各点到树的距离均为无穷大，无法生成MST，返回-1 sum+=minn;//加上路径 now=index;//新的元素加入树 for(int j=0;j<vec[now].size();j++) { if(vec[now][j].w<dis[vec[now][j].des]) dis[vec[now][j].des]=vec[now][j].w; //遍历新的元素和其余各点的距离，更新各点到树的最小距离 } } return sum; } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int a,b,len; scanf("%d%d%d",&a,&b,&len); ed1.des=a,ed2.des=b,ed1.w=ed2.w=len; vec[a].push_back(ed2); vec[b].push_back(ed1); } int ans=prim(); if(ans==-1) cout<<"There is no minimum spanning tree"; else cout<<ans; return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
10.1.2 Kruskal算法
#includeusing namespace std; int n,e,i; int F[1501]; struct Edge { int from; int to; int w; }edge[1501]; bool cmp(Edge x,Edge y) { return x.w<y.w; } int find(int x) { if(F[x]==x) return F[x]; else return F[x]=find(F[x]); } bool fun(int a,int b) { int x=find(a); int y=find(b); if(x!=y) { F[y]=x; return true; } return false; } int main() { scanf("%d%d",&n,&e) int total=0,cnt=0; for(i=0;i<e;i++) scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].w); for(i=0;i<n;i++) F[i]=i; sort(edge,edge+e,cmp); for(i=0;i<e;i++) { if(fun(edge[i].from,edge[i].to)) { total+=edge[i].w; cnt++; } if(cnt==n-1) break; } if(cnt==n-1) printf("%d\n",total); else cout<<"There is no minimum spanning tree."<<endl; return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
10.2 拓扑排序
设 G为有 n 个顶点的带权有向无环图，G 中各顶点的编号为 1 到 n，请设计算法，计算图 G 中 1, n 间的最长路径。
//45ms / 3.10MB / 892B C++14 (GCC 9) O2 #includeusing namespace std; queue<int>q; int n,m; int maxn[1510],mark[1510],ind[1510]; //maxn：到当前结点之前的最长路 //mark:标记“在路径上” //ind:记录每个结点的入度 struct Edge { int from; int to; int w; }edge[50010]; vector<Edge>vec[50010];//vec为Edge型的，在已知起点时可直接通过这个调用出边权和终点 void topo_sort()//拓扑排序 { for (int i=1;i<=n;i++) if (ind[i]==0) q.push(i);//先将所有入度为0 的结点放入队列 while(q.size()) { int now=q.front();//每次取出队首元素 q.pop(); for(int j=0;j<vec[now].size();j++)//遍历队首元素指向的所有结点 { ind[vec[now][j].to]--;//去掉当前结点的同时，它指向的所有结点入度减1 if(mark[now])//在路径上 { if(maxn[vec[now][j].to]<maxn[now]+vec[now][j].w) maxn[vec[now][j].to]=maxn[now]+vec[now][j].w; //如果from之前的最长路加上边权大于之前获得的to之前的最长路，就更新一下 mark[vec[now][j].to]=1;//标记终点在路径上 } if(!ind[vec[now][j].to]) //删边操作之后终点的入度变为0，则将其压入队列 q.push(vec[now][j].to); } } } int main() { int i; cin>>n>>m; for(i=0;i<m;i++) { scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].w); vec[edge[i].from].push_back(edge[i]); ind[edge[i].to]++; } maxn[n]=-1; mark[1]=1;//标记起点（1）在路径上 topo_sort(); cout<<maxn[n]; return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
10.3 最短路
10.3.1 Dijkstra算法
#includeusing namespace std; #define INF 0x3ffffff struct Node { int v,l;//一条路的尾结点，该路的长度 }; int n,e,from,to; vector<Node> v[1001]; int dis[1001]; int path[1001]; int visit[1001]; void Dijkstra(int from) { fill(dis,dis + 1001,INF); dis[from] = 0; for(int i = 0;i < n;i ++) { int u = -1,minx = INF; for(int j = 0;j < n;j ++) { if(visit[j] == 0 && dis[j] < minx) { minx = dis[j]; u = j; } } if(u == -1) break; visit[u] = 1; for (int j = 0; j < v[u].size(); j++) { int x = v[u][j].v; if (visit[x] == 0 && dis[u] + v[u][j].l < dis[x]) { dis[x] = dis[u] + v[u][j].l; path[x] = u; } } } } int main() { cin >> n >> e; for (int i = 0; i < e / 2; i++) { int a, b, c; cin >> a >> b >> c; v[a].push_back(Node{b, c}); v[b].push_back(Node{a, c}); } cin >> from >> to; if (from == to) { printf("%d-->%d:0",from,from); return 0; } Dijkstra(from); vector<int> ve; int x = to; while (x != from) { ve.push_back(x); x = path[x]; } cout << from; for (int i = ve.size() - 1; i >= 0; i--) cout << "-->" << ve[i]; cout << ":" << dis[to]; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
单调队列优化：
将常规版本的Dijkstra 中每个结点遍历所有相邻结点找到距离最近的这一步用堆优化，每次直接从小根堆中直接取出顶点，可以将时间复杂度降到O(VlogV)。
// 309ms / 7.68MB / 1.02KB C++14 (GCC 9) O2 #includeusing namespace std; const int N=1e5+10; int n,m,s; int dis[N],vis[N]; struct Node { int to,w; bool operator < (const Node& x) const { return w>x.w; } }; vector<Node> vec[N]; priority_queue<Node>q; //默认大根堆（从头取数据从大到小），运算符重载后现在为小根堆 void Dijkstra() { memset(dis,0x3f,sizeof(dis));//距离初始化为无穷大 dis[s]=0; Node now; now.to=s,now.w=0; q.push(now);//起点入队 while(!q.empty()) { int next=q.top().to;//取出队顶元素（距离最小的） q.pop(); if(vis[next]) continue;//已经访问过了就下一个 vis[next]=1;//标记已经访问过 for(int i=0;i<vec[next].size();i++)//遍历当前结点相邻的所有结点 { if(vec[next][i].w+dis[next]<dis[vec[next][i].to])//松弛操作 { dis[vec[next][i].to]=vec[next][i].w+dis[next]; now.to=vec[next][i].to; now.w=dis[vec[next][i].to]; q.push(now); } } } } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); Node no; no.to=b; no.w=c; vec[a].push_back(no); } Dijkstra(); for(int i=1;i<=n;i++) printf("%d ",dis[i]); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
10.3.2 SPFA算法
给出一个N个顶点M条边的无向无权图，顶点编号为1-N。问从顶点1开始，到其他每个点的最短路有几条。
// 1:50ms / 3.21MB / 863B C++14 (GCC 9) O2 // 2:48ms / 3.13MB / 877B C++14 (GCC 9) O2 #includeusing namespace std; const int mod=100003,N=1000010; int n,m,ans[N],minn[N],vis[N]; struct edge { int a,b; }e[N*2]; vector<int>vec[N]; queue<int>q; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void SPFA(int start) { minn[start]=0,ans[start]=1,vis[start]=1; q.push(start); int now; while(q.size()) { now=q.front(); q.pop(); for(int i=0;i<vec[now].size();i++) { if(!vis[vec[now][i]]) { vis[vec[now][i]]=1; if(minn[vec[now][i]]>minn[now]+1) minn[vec[now][i]]=minn[now]+1; q.push(vec[now][i]); } if(minn[vec[now][i]]==minn[now]+1) ans[vec[now][i]]=(ans[vec[now][i]]+ans[now])%mod; } } } int main() { memset(minn,127,sizeof(minn)); n=read(),m=read(); for(int i=0;i<m;i++) { int x,y; x=read(),y=read(); if(x==y) continue; vec[x].push_back(y); vec[y].push_back(x); } SPFA(1); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
10.3.3 Floyd算法
#includeusing namespace std; #define N 1000 int n,m,x,y,z,posx=-1,posy=-1,max1; int maps[N][N]; int path[N][N]; int pre[N]; void f(int x,int y) { int k=path[x][y]; if(k==-1){//找不到更近的 pre[y]=x; return; } f(k,y); f(x,k); } void print(int x,int y) { if(x==y) { cout<<x; return; } print(x,pre[y]); cout<<"->"<<y; return; } int main() { memset(path,-1,sizeof(path)); cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j) maps[i][j]=0x3ffffff; for(int i=1;i<=m;i++) { cin>>x>>y>>z; if(maps[x][y]>z) maps[x][y]=z; } for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(maps[i][j]>maps[i][k]+maps[k][j]) { maps[i][j]=maps[i][k]+maps[k][j]; path[i][j]=k; } int t=2; while(t--) { cin>>x>>y; if(x==y) cout<<x<<"->"<<y<<":0"<<endl; else { if(maps[x][y]==0x3ffffff) cout<<x<<"->"<<y<<":-1"<<endl; else { memset(pre,0,sizeof(pre)); f(x,y); print(x,y); cout<<":"<<maps[x][y]<<endl; } } } for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(maps[i][j]!=0x3ffffff&&maps[i][j]>max1) { max1=maps[i][j]; posx=i; posy=j; } memset(pre,0,sizeof(pre)); if(posx!=-1&&posy!=-1) { f(posx,posy); print(posx,posy); cout<<":"<<maps[posx][posy]<<endl; } else cout<<endl; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
10.3.4 次短路
#include#include #include using namespace std; const int N=5020; const int R=200010; int n,r; int dis[R],vis[R],ver[R],nex[R],val[R][2],head[R],tot=0; queue<int>q; int read() { int sum=0,fg=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')fg=-1;c=getchar();} while(c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();} return sum*fg; } void add1(int x,int y,int z) { //edge[++tot].nxt=head[x],edge[tot].to=y,edge[tot].dis=z,head[x]=tot; nex[++tot]=head[x],ver[tot]=y,dis[tot]=z,head[x]=tot; } /*void spfa(int start) { memset(val,0x7f,sizeof(val)); vis[start]=1,val[start][0]=0; q.push(start); while(!q.empty()) { int now=q.front(); vis[now]=0; q.pop(); for(int i=head[now];i;i=nex[i]) { int to=ver[i]; if(val[now][0]+dis[i] - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
10.4 负环
负环判断
#includeusing namespace std; const int N=10010; int T,n,m; int head[N],ver[N],nex[N],tot,vis[N],cnt[N],val[N],dis[N]; queue<int>q; void add(int x,int y,int z) { ver[++tot]=y,nex[tot]=head[x],head[x]=tot,val[tot]=z; if(z>=0) ver[++tot]=x,nex[tot]=head[y],head[y]=tot,val[tot]=z; } void init() { tot=0; memset(head,0,sizeof(head)); memset(ver,0,sizeof(ver)); memset(nex,0,sizeof(nex)); memset(vis,0,sizeof(vis)); memset(val,0,sizeof(val)); memset(cnt,0,sizeof(cnt)); memset(dis,0x3f,sizeof(dis)); while(!q.empty()) q.pop(); } bool spfa() { vis[1]=1,dis[1]=0; q.push(1); while(q.size()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head[now];i;i=nex[i]) { int to=ver[i]; if(dis[now]+val[i]<dis[to]) { dis[to]=dis[now]+val[i]; if(!vis[to]) { cnt[to]=cnt[now]+1; if(cnt[to]>=n) return true; vis[to]=1,q.push(to); } } } } return false; } int main() { cin>>T; while(T--) { init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } if(spfa()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
10.5 二分图
#includeusing namespace std; const int N=520; int n,m,e,tot,ans; int mp[N][N],vis[N],match[N]; bool dfs(int x) { for(int i=1;i<=m;i++) { if(!mp[x][i]||vis[i]) continue; vis[i]=1; if(!match[i]||dfs(match[i])) { match[i]=x; return true; } } return false; } int main() { cin>>n>>m>>e; for(int i=1;i<=e;i++) { int x,y; scanf("%d%d",&x,&y); mp[x][y]=1; } for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } cout<<ans; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
10.6 欧拉路径
欧拉路径：欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边通过的且只通过一次。
欧拉回路:欧拉回路是指起点和终点相同的欧拉路。
对于无向图，所有边都是连通的
（1）存在欧拉路径的充分必要条件：度数为奇数的点只能是0个或者2个
（2）存在欧拉回路的充分必要条件：度数为奇数的只能是0个
2对于有向图，所有边都是连通的
（1）存在欧拉路径的充分必要条件：要么所有点的出度均等于入度， 要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点：一个满足出度比入度多1（起点），另一个满足入度比出度多1（终点）（2）存在欧拉回路的充分必要条件：所有点的出度均等于入度
求有向图字典序最小的欧拉路径。
#includeusing namespace std; const int N=100010; int n,m,start=1; int ind[N],outd[N],p[N]; vector<int>vec[N]; stack<int>st; void dfs(int now) { for(int i=p[now];p[now]<vec[now].size();i++) { p[now]++; //cout<<"p[now]:"< - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
-
相关阅读:
magical_spider远程采集方案
力扣 1656. 设计有序流
Go context 原理（channel广播机制 + mutex线程安全）
外包干了一个月，技术明显进步。。。。。
即时通讯开发之MobileIMSDK-Web介绍
perl 用 XML::LibXML 解析 Freeplane.mm文件，
Neo4j图数据库和GDS图算法应用
pytorch中的view与reshape
（三）SvelteKit教程：layout 文件
SSM学习——spring整合mybatis与junit（7）
- 原文地址：https://blog.csdn.net/m0_60630928/article/details/126468185
