Loading... --- title: " 清北学堂noip2018集训D4\t\t" tags: - 图论 url: 31.html id: 31 categories: - OI - 集训 date: 2019-03-09 16:24:45 --- > #### P.S. > > 最小生成树，最短路问题，SPFA算法，强连通分量。 <!--more--> 图的读入 ---- * n m m行，u，v 例如： 6 8 1 2 1 3 2 4 3 4 3 5 4 1 4 6 5 6  * 6 8 1 1 1 2 1 5 2 5 2 3 3 4 4 5 4 6  * 一些术语 * 简单图：无重边，无自环。 * 路径：一组首尾相连的边的集合 * 度数（入度，出度）：连接一个点的边的数量。 * 连通图：图中任意两点都有路径连接。 * 连通分量（联通块）：极大的联通子图。 * 完全图：任意两点有边相连。n个点的完全图有$n(n-1)/2$。 * 有向无环图（DAG） * ### 图的存储 * 用的方便？ * 检查两点之间是否有边。 * 遍历（枚举）一个点的所有出边。 * \#### 邻接矩阵 * 检查两点之间是否有边。  * 注意空间 * 256 MB * 256\*1024\*1024 B * bool 1B * int 4B * long long 8B * double 8B * 时间 * 1s $10^7$ O(n) * 代码如下 `cpp #include<bits/stdc++.h> using namespace std; int n,m; // n*n int graph[105][105]; int main(){ scanf("%d%d",&m,&n); int x,y; for(int i=0;i<n;i++){ scanf("%d%d",&x,&y); x--;y--; graph[x][y]=1; graph[y][x]=1; //重边：graph[x][y]++; //graph[x][y]++; //权值：graph[x][y]=z; //graph[y][x]=z; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cout<<graph[i][j]<<" "; } cout<<endl; } return 0; }` * #### 邻接表 * 遍历（枚举）一个点的所有出边。 * n个链表 * 对于每个点，开一个链表，链表存储当前这个点的所有出边。 * 1 .vector存图 STL 可变长数组 * 2 . 数组链表 * 代码如下： #include<bits/stdc++.h> using namespace std; int n,m; vector<int> a[10005]; int graph[105][105]; int main(){ scanf("%d%d",&m,&n); int x,y; for(int i=0;i<n;i++){ scanf("%d%d",&x,&y); a[x].push_back(y); a[y].push_back(x);//无向图 } int w=3; for(int i=0;i<a[w].size();i++){ cout<<a[w][i]<<" "; } return 0; } * 链表存储 * 代码如下： #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个节点 这条边指向图中的点 int head[10005],nxt[30005], ver[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y){ // 在x的链表中 加一条指向y的边 ++tot; // 当前链表节点就是编号为tot ver[tot]=y; nxt[tot]=head[x]; head[x]=tot; } int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x);//无向图 } // 遍历一个点的所有出边 int x=5; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; printf("%d ",y); } return 0; } * 带权值： #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个节点 这条边指向图中的点 边的权值 int head[10005],nxt[30005], ver[30005] , w[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y,int z){ // 在x的链表中 加一条指向y的边 权值为z ++tot; // 当前链表节点就是编号为tot ver[tot]=y; w[tot]=z; nxt[tot]=head[x]; head[x]=tot; } int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);//无向图 } // 遍历一个点的所有出边 int x=5; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; printf("%d %d ",y,w[i]); } return 0; } * #### 遍历图 * dfs * 代码： #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个节点 这条边指向图中的点 int head[10005],nxt[30005], ver[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y){ // 在x的链表中 加一条指向y的边 ++tot; // 当前链表节点就是编号为tot ver[tot]=y; nxt[tot]=head[x]; head[x]=tot; } bool vis[10005]; void dfs(int x){ printf("%d ",x); vis[x]=1; for(int i=head[x];i;i=nxt[i]){ if(!vis[ver[i]]){ dfs(ver[i]); } } } int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x);//无向图 } dfs(1); return 0; } * bfs * 代码： #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个链表节点 这条边指向图中的点 int head[10005],nxt[30005], ver[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y){ // 在x的链表中 加一条指向y的边 ++tot; // 当前链表节点就是编号为tot ver[tot]=y; nxt[tot]=head[x]; head[x]=tot; } bool vis[10005]; // 是否已经入队 int d[10005]; // 到起点的距离 queue<int> q; // 队列 // q.front() 队列的第一个元素 // q.push(x) 把x加入到队列中 // q.pop()弹出第一个数字 // q.empty()返回队列是否为空 // q.size()队列里还有多少元素 int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x);//无向图 } // 遍历一个点的所有出边 // int x=5; // for(int i=head[x];i;i=nxt[i]){ // int y=ver[i]; // printf("%d ",y); // } // // 重复入队 // while(!q.empty()) { // int x=q.front();q.pop(); // vis[x] = 1; // // do something // // for(int i=head[x];i;i=nxt[i]){ // if(!vis[ver[i]]){ // q.push(ver[i]); // } // } // } q.push(1);vis[1]=1; /// !!!! while(!q.empty()) { int x=q.front();q.pop(); // do something for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(!vis[y]){ vis[y] = 1; d[y] = d[x] + 1 ; q.push(y); } } } for(int i=1;i<=n;i++){ printf("%d ",d[i]); } return 0; } * #### 最短路 * 多源最短路 * Floyd * 考虑用dp解决这个问题； * $dp\[i\]\[j\]\[k\]=min(dp\[i-1\]\[j\]\[i\]+dp\[i-1\]\[i\]\[k\],dp\[i-1\]\[j\]\[k\])$ * $dp\[j\]\[k\]=min(dp\[j\]\[i\]+dp\[i\]\[k\],dp\[j\]\[k\])$ * 代码： #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; // n*n // 100000 200000 int graph[105][105]; // 边权>0 int floyd[105][105]; int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y,z;i<m;i++){ scanf("%d%d%d",&x,&y,&z); graph[x][y]=z; } memset(floyd,0x3F,sizeof(floyd)); for(int i=1;i<=n;i++) floyd[i][i] = 0; // 初始值 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(graph[i][j]) floyd[i][j]=graph[i][j]; } } // floyd O(n^3) for(int k=1;k<=n;k++){ // 循环顺序注意 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]); } } } int xx,yy; scanf("%d%d",&xx,&yy); printf("%d",floyd[xx][yy]); return 0; } * 单源最短路 * 求一个点到每个点的最短路 * Dijkstra 迪杰斯特拉算法 * SFPA算法 * Dijkstra 迪杰斯特拉算法 1. 从所有点中选择未标记的$dis\[i\]$值最小的顶点$i$，将$i$标记； 2. 松弛节点$i$的相邻节点 3. 若所有点都被标记，结束。否则回到1 4. 代码： #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个节点 这条边指向图中的点 边的权值 int head[10005],nxt[30005], ver[30005] , w[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y,int z){ // 在x的链表中 加一条指向y的边 权值为z ++tot; // 当前链表节点就是编号为tot ver[tot]=y; w[tot]=z; nxt[tot]=head[x]; head[x]=tot; } struct N{ int x,w; // x节点，w 当前d[x]的值 friend bool operator < (N a,N b){ // C++重载运算符 return a.w>b.w; } N(int a=0,int b=0){ // 构造函数 x=a,w=b; } }; priority_queue<N> pq; int d[10005]; bool vis[10005] int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);//无向图 } int s=1; memset(d,0x3f,sizeof d); // 0x3f3f3f3f d[s]=0; pq.push(N(s,d[s]); // pq.push((N){s,d[s]}); while(!pq.empty()){ int x=pq.top().x;pq.pop(); if(vis[x]) continue; else vis[x]=1; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(d[y]>d[x]+w[i]){ d[y]=d[x]+w[i]; pq.push(N(y,d[y])); } } } // d[] // d[x] == 0x3f3f3f3f 不连通 return 0; } * 带计数的算法（多个最短路） #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个节点 这条边指向图中的点 边的权值 int head[10005],nxt[30005], ver[30005] , w[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y,int z){ // 在x的链表中 加一条指向y的边 权值为z ++tot; // 当前链表节点就是编号为tot ver[tot]=y; w[tot]=z; nxt[tot]=head[x]; head[x]=tot; } struct N{ int x,w; // x节点，w 当前d[x]的值 friend bool operator < (N a,N b){ // C++重载运算符 return a.w>b.w; } N(int a=0,int b=0){ // 构造函数 x=a,w=b; } }; priority_queue<N> pq; int d[10005]; // 最短路的权值 int cnt[10005]; // 最短路的条数 bool vis[10005] int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);//无向图 } int s=1; memset(d,0x3f,sizeof d); // 0x3f3f3f3f d[s]=0; cnt[s] = 1; pq.push(N(s,d[s]); // pq.push((N){s,d[s]}); while(!pq.empty()){ int x=pq.top().x;pq.pop(); if(vis[x]) continue; else vis[x]=1; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(d[y]>d[x]+w[i]){ d[y]=d[x]+w[i]; cnt[y]=cnt[x]; pq.push(N(y,d[y])); }else if(d[y] == d[x]+w[i]){ cnt[y]+=cnt[x]; } } } // d[] // d[x] == 0x3f3f3f3f 不连通 return 0; } * POJ 2387 * SPFA * 流程： 1. 将源点S出队。 2. 从队列里取出头的点v，用原点到v的**当前最短距离**来更新源点到与v相邻的点的最短距离（松弛操作） 3. 将最短距离更新过且不在队列中的点入队。 4. 回到第二步，直到队列为空为止。 * 最坏情况$O(nm)$，大多数$O(m)/O(km)$ * 可以处理负权。 * 在稀疏图效率较高。 * 示例代码： #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个节点 这条边指向图中的点 边的权值 int head[10005],nxt[30005], ver[30005] , w[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y,int z){ // 在x的链表中 加一条指向y的边 权值为z ++tot; // 当前链表节点就是编号为tot ver[tot]=y; w[tot]=z; nxt[tot]=head[x]; head[x]=tot; } queue<int> q; int d[10005]; bool inq[10005]; int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);//无向图 } int s=1; memset(d,0x3f,sizeof d); // 0x3f3f3f3f d[s]=0; q.push(s); inq[s]=1; while(!q.empty()){ int x=q.front();q.pop(); inq[x]=0; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(d[y]>d[x]+w[i]){ d[y]=d[x]+w[i]; if(!inq[y]) inq[y]=1,q.push(y); } } } // d[] // d[x] == 0x3f3f3f3f 不连通 return 0; } * #### 最小生成树 * 生成树：选出一个图的$n-1$条边，使其构成一棵树。 * 最小生成树（MST）：边权和最小的那个生成树。  * Prim * Prim算法是通过先获取一个点，然后不断加入点的一个过程。 * 初始化：$V^’=x,E^’=\\varnothing$，x是随便一个节点。 * 重复下列操作，直到$V^’=V$ * 在E集合当中选择最小的边<u,v>使得$u\\in V^’但是v\\notin V^’$; * $V^’$加入节点v，$E^’$加入<u,v> * $(V^’,E^’)$为最小生成树。 * 类似Dijkstra. * 示例代码： #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个节点 这条边指向图中的点 边的权值 int head[10005],nxt[30005], ver[30005] , w[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y,int z){ // 在x的链表中 加一条指向y的边 权值为z ++tot; // 当前链表节点就是编号为tot ver[tot]=y; w[tot]=z; nxt[tot]=head[x]; head[x]=tot; } struct N{ int x,w; // x节点，w 当前d[x]的值 friend bool operator < (N a,N b){ // C++重载运算符 return a.w>b.w; } N(int a=0,int b=0){ // 构造函数 x=a,w=b; } }; priority_queue<N> pq; bool vis[10005] int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);//无向图 } int s=1; d[s]=0; pq.push(N(s,0); int sum = 0; // pq.push((N){s,d[s]}); while(!pq.empty()){ int x=pq.top().x; sum+=pq.top().w; pq.pop(); if(vis[x]) continue; else vis[x]=1; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(!vis[y]){ pq.push(N(y,w[i])); } } } // sum 最小生成树的权值和 return 0; } * Kruskal * 给所有边按照边权从小到大的顺序排序； * 从小到大依次考虑每条边(u,v)（最开始没有任何的边）: * 如果u 与v 已经连通了，那么加入(u,v) 后会出现环，不添加 * 如果u 与v 没有连通，那么加入(u,v) 使其连通 * 并查集维护连通性。 * 代码如下： #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; int n,m; int fa[1000005]; // fa[x] x在并查集树上的父亲是谁 int get(int x){ // 返回x在并查集树上的根 if(fa[x] == x) return x; return fa[x]=get(fa[x]); // 路径压缩 } void merge(int x,int y){ // 合并x所在集合 和 y所在集合 x=get(x); y=get(y); fa[x]=y; } struct Edge{ int x,y,z; }edge[1000005]; bool cmp(Edge&a,Edge&b){ return a.z<b.z; } int main(){ scanf("%d%d",&n,&m); // 并查集初始化 for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){ scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z); } sort(edge+1,edge+m+1,cmp); int sum = 0; for(int i=1;i<=m;i++){ int u=edge[i].x,v=edge[i].y; if(get(u)!=get(v)){ merge(u,v); sum+=edge[i].z; } } printf("%d",sum); // 货车运输 /* for(int i=1;i<=m;i++){ // 相同边权的边 int u=edge[i].x,v=edge[i].y; if(get(u)!=get(v)){ // i sum+=edge[i].z; } } for(int i=1;i<=m;i++){ // 相同边权的边 int u=edge[i].x,v=edge[i].y; if(get(u)!=get(v)){ merge(u,v); // i之前是可以 加进MST， 现在不行 sum+=edge[i].z; } } */ return 0; } * POJ 2421 constructing roads * POJ 1789 Truck History * POJ1679 判断最小生成树的唯一性 * 拓扑排序 ---- * 有向无环图  * 拓扑序指的是可以把所有点写成一个序列，使得所有边都是从前面的点连向后面的点。 * DAG 可以进行拓扑排序。 * 维护一个入度为0 的顶点的集合，每次从该集合中任意取出一个顶点，将该顶点放入保存结果的List 中。紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为0，那么也将这个顶点放到入度为0 的集合中。然后继续从集合中取出一个顶点，重复操作。 * 当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果List，此List 中的顺序就是对图进行拓扑排序的结果。 * $O(n + m)$ * 代码如下： #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int n,m; // 数组链表 邻接表 // 链表头 链表节点的下一个节点 这条边指向图中的点 int head[10005],nxt[30005], ver[30005]; int tot;// 记录链表节点用了多少个 void add(int x,int y){ // 在x的链表中 加一条指向y的边 ++tot; // 当前链表节点就是编号为tot ver[tot]=y; nxt[tot]=head[x]; head[x]=tot; } int indegree[10005]; int a[10005]; queue<int> q; int main(){ scanf("%d%d",&n,&m); for(int i=0,x,y;i<m;i++){ scanf("%d%d",&x,&y); add(x,y); indegree[y]++; } for(int i=1;i<=n;i++){ if(indegree[i] == 0) q.push(i); } int cnt=0; while(!q.empty()){ int x=q.front();q.pop(); a[++cnt] = x; for(int i=head[x];i;i=nxt[i]){ indegree[ver[i]] -- ; if(indegree[ver[i]]==0){ q.push(ver[i]); } } } for(int i=1;i<=n;i++){ printf("%d ",a[i]); } return 0; } Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏