\(Day\) \(4\)
图论
图论主要分为\(4\)个方面
1.最短路
2.二分图匹配
3.生成树
4.强连通(这个超纲了,不讲)
在介绍完理论知识后,我们会逐一讨论它们
图
图是由点和边构成的
边又分为有向边和无向边,因此图可以分为有向图和无向图
无向图的度指的是一个点连了多少条边
有向图的入度指的是有多少条边指向这个点,出度指的是有多少条边从这个点出发
树
树是特殊的图
树包含以下三个性质:
- 无向
- 无环
- 连通
连通指的是从任一点出发,可以走到任一点
例如
一个\(n\)个点的树,必然有\(n-1\)条边
一个树的中心点我们一般称之为根
根的下面几个点叫儿子
从\(i\)点走到根所经过的所有点,叫做这个点的祖先
从\(i\)点走到\(j\)点只有一种走法
\(k\)叉树
每个点最多有\(k\)个儿子的树
\(2\)叉树
这是一个二叉树:
它有\(3\)种遍历方法:
- 前序:根左右
- 中序:左根右
- 后序:左右根
这个二叉树的前序是\(124563789\)
中序是\(426513879\)
后序是\(425689731\)
完全二叉树:有右必有左
满二叉树:每一层都是满的(或者从左到右是满的)
森林
森林是对连通没有要求的树,一棵树也是一个森林
有向树
有向树是有方向的树
它分为内向树和外向树
外向树指能找到一个点,可以让它指向所有点
反之就是内向树
章鱼图(基环树)
\(n\)个点的章鱼图有\(n\)条边
先去掉一条边,就变成了一个树,其边数就是\(n-1\),再加上那一条边就是\(n\)条边
二分图
可以把所有点分成两部分,使得部分内部没有边
这就是一个二分图
树一定是二分图
如果有奇数个环,这个图就是二分图
存储图
邻接矩阵
#include<iostream>
using namespace std;
const int maxn=1010;
int n,m,z[maxn][maxn];
//n代表图的点数
//m代表图的边数
//z[i][j] 就代表 从 i 到 j那条边的信息(长度)
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int s,e,d;//这是一条从s到e 长度为d的边
cin >> s >> e >> d;
z[s][e] = d;//存储到z[s][e]
z[e][s] = d;//如果是无向图 就反着再建一条边
}
return 0;
}
边表(邻接表)
#include<iostream>
using namespace std;
const int maxn=100010;
const int maxm=200010;
int n,m,en,first[maxn];
//n代表点数
//m代表边数
//en代表当前已经插入几条边
//first[i] 代表从i点出发的第一条边的编号
struct edge
{
int e,d;//这条边的终点为e 长度为d
int next;//下一条边的编号为next
edge() {
e=d=next=0;
}
}ed[maxm];//ed[i]就代表编号为i的边
void add_edge(int s,int e,int d)//添加一条从s到e 长度为d的边
{
en++;//边的数量+1
ed[en].e = e;//记录新的这条边的终点
ed[en].d = d;//记录新的这条边的长度
ed[en].next = first[s];//新加的这条边的下一条边 应该是 原来从s出发的第一条边
first[s] = en;//让en作为s出发的第一条边
}
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int s,e,d;//这是一条从s到e 长度为d的边
cin >> s >> e >> d;
add_edge(s,e,d);
add_edge(e,s,d);//如果是无向图
}
for (int i=1;i<=n;i++)
for (int j=first[i];j!=0;j=ed[j].next)//遍历从i出发的每一条边
cout << i << "->" << ed[j].e << "=" << ed[j].d << endl;
}
比较
邻接矩阵 | 边表 | |
---|---|---|
优点 | 速度快 | 空间小,可以存储重边 |
缺点 | 空间大,不可以处理重边 | 速度慢 |
当\(n\le 1000\)时,用邻接矩阵,否则使用边表
\(problem\) 1
给你\(n\)个点\(m\)条边的无向图,判断是不是二分图
\(DFS\)
#include<iostream>
using namespace std;
const int maxn=100010;
const int maxm=200010;
int n,m,en,first[maxn];
//n代表点数
//m代表边数
//en代表当前已经插入几条边
//first[i] 代表从i点出发的第一条边的编号
struct edge
{
int e;//这条边的终点为e
int next;//下一条边的编号为next
edge() {
e=next=0;
}
}ed[maxm];//ed[i]就代表编号为i的边
void add_edge(int s,int e)//添加一条从s到e
{
en++;//边的数量+1
ed[en].e = e;//记录新的这条边的终点
ed[en].next = first[s];//新加的这条边的下一条边 应该是 原来从s出发的第一条边
first[s] = en;//让en作为s出发的第一条边
}
int col[maxn];//col[i]代表i点被染上了什么颜色 0:还没被染色 1:红色 2:蓝色
void dfs(int now)//搜索now点 将now周围的点染色
{
for (int i=first[now];i!=0;i=ed[i].next)//枚举从now出发的所有边
{
int j=ed[i].e;//是一条从now -> j的边
if (col[j] == 0)//j点还没有被染色过
{
col[j] = 3 - col[now];
dfs(j);//再去把j点周围染色
}
else//j点在之前已经被染过色了
{
if (col[j] == col[now])
{
cout << "no" << endl;
exit(0);//退出整个程序
}
}
}
}
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int s,e,d;//这是一条从s到e 长度为d的边
cin >> s >> e;
add_edge(s,e);
add_edge(e,s);//如果是无向图
}
//dfs染色
for (int i=1;i<=n;i++)
if (col[i] == 0)
{
col[i] = 1;
dfs(i);
}
cout << "yes" << endl;
}
\(BFS\)
#include<iostream>
#include<queue>
using namespace std;
const int maxn=100010;
const int maxm=200010;
int n,m,en,first[maxn];
//n代表点数
//m代表边数
//en代表当前已经插入几条边
//first[i] 代表从i点出发的第一条边的编号
struct edge
{
int e;//这条边的终点为e
int next;//下一条边的编号为next
edge() {
e=next=0;
}
}ed[maxm];//ed[i]就代表编号为i的边
void add_edge(int s,int e)//添加一条从s到e
{
en++;//边的数量+1
ed[en].e = e;//记录新的这条边的终点
ed[en].next = first[s];//新加的这条边的下一条边 应该是 原来从s出发的第一条边
first[s] = en;//让en作为s出发的第一条边
}
int col[maxn];//col[i]代表i点被染上了什么颜色 0:还没被染色 1:红色 2:蓝色
queue<int> q;//已经被染色过 但还没有去染色周围节点的点
void bfs(int now)//搜索now点 将now周围的点染色
{
q.push(now);
while (q.size() != 0)//队列不为空 还有点需要对周围点进行染色
{
int p=q.front();//对p点周围所有点进行染色
q.pop();
for (int i=first[p];i!=0;i=ed[i].next)//枚举从p出发的所有边
{
int j = ed[i].e;//这条边是从p到j的一条边
if (col[j] == 0)//j点仍未被染色
{
col[j] = 3-col[p];
q.push(j);
}
else
{
if (col[j] == col[p])
{
cout << "no" << endl;
exit(0);
}
}
}
}
}
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int s,e,d;//这是一条从s到e 长度为d的边
cin >> s >> e;
add_edge(s,e);
add_edge(e,s);//如果是无向图
}
//dfs染色
for (int i=1;i<=n;i++)
if (col[i] == 0)
{
col[i] = 1;
bfs(i);
}
cout << "yes" << endl;
}
二分图匹配
要怎么做呢
匈牙利算法
#include<iostream>
using namespace std;
int n,m,k;//n代表左边有几个点 m代表右边有几个点
//k有多少条边
bool match[maxn][maxn];//match[i][j] 代表 左边第i个点 和 右边第j个点 能不能匹配
int result[maxn];//result[i] 代表右边第i个点和 左边第result[i]个点 已经匹配上了
bool use[maxn];//use[i] 代表右边第i个点 在当前轮中有没有被请求过匹配
bool dfs(int l)//让左边第l个点尝试匹配 如果能匹配成功返回true 否则返回false
{//O(n^3) 边表去实现: O(n边数)
for (int r=1;r<=m;r++)//枚举右边每一个点
if (match[l][r] && use[r]==false)//如果左边第l个点和右边第r个点能匹配
//右边第r个点没有被请求过匹配
{
use[r]=true;//右边第r个点被请求匹配了
if (result[r] == 0 || dfs(result[r]))//要么右边第r个点没有匹配
//要么和右边第r个点匹配的点result[r] 可以重新匹配成功
{
result[r] = l;
return true;
}
}
return false;//匹配失败
}
int main()
{
cin >> n >> m >> k;
for (int i=1;i<=k;i++)
{
int l,r;
cin >> l >> r;
match[l][r] = true;//左边第l个点 和 右边第r个点可以匹配
}
int ans=0;
for (int i=1;i<=n;i++)//枚举左边每个点 让左边每个点去尝试匹配
{
memset(use,false,sizeof(use));
if (dfs(i)) ans++;
}
cout << ans << endl;
return 0;
}
生成树
在一个图中,找出一个有\(n\)个点和\(n-1\)条边组成的树
每个生成树的大小就是边长之和
最小生成树问题:找出最小的生成树
\(kruscal\)算法
先对每条边由小到大排序,在从最小的边开始组成一棵生成树
#include<iostream>
#include<algorithm>
using namespace std;
struct edge
{
int p1,p2,d;//这是一条在p1 和 p2之间长度为d的边
}ed[maxm];//ed[i]代表第i条边
//bool cmp(const edge &a,const edge &b)//a是否应该放在b的前面
bool operator<(const edge &a,const edge &b)
{
return a.d<b.d;
}
int to[maxn];
int go(int p)
{
if (p==to[p]) return p;
else return to[p]=go(to[p]);
}
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
cin >> ed[i].p1 >> ed[i].p2 >> ed[i].d;
}
//sort(ed+1,ed+m+1,cmp);
sort(ed+1,ed+m+1);//把所有边从小到大排序 O(mlogm)
for (int i=1;i<=n;i++)
to[i] = i;
int ans=0,cnt=0;//cnt代表到底取了多少条边
for (int i=1;i<=m;i++)//尝试向生成树中加入第i条边 O(m)
{
int p1=ed[i].p1;
int p2=ed[i].p2;
if (go(p1) != go(p2))//加入这条边之后不会有环
{
ans += ed[i].d;
cnt ++;
to[go(p1)] = go(p2);
}
}
cout << ans << endl;
return 0;
}
\(problem\) \(2\)
求一个最小生成树,尽量用白边,看生成树最多能用多少条白边
在尽量不用白边,看最少能用多少条白边
看斐波那契额数列的第几项在这两个值之间
\(problem\) \(3\)
从一个点走到另一个点的最短路径叫做\(LCA\)
怎么算距离?
怎么算\(LCA\)?
倍增法
\(f\)怎么求?怎么用?
#include<iostream>
using namespace std;
const int maxn=100010;
const int maxm=200010;
int n,m,en,first[maxn];
//n代表点数
//m代表边数
//en代表当前已经插入几条边
//first[i] 代表从i点出发的第一条边的编号
struct edge
{
int e;//这条边的终点为e
int next;//下一条边的编号为next
edge() {
e=next=0;
}
}ed[maxm];//ed[i]就代表编号为i的边
void add_edge(int s,int e)//添加一条从s到e
{
en++;//边的数量+1
ed[en].e = e;//记录新的这条边的终点
ed[en].next = first[s];//新加的这条边的下一条边 应该是 原来从s出发的第一条边
first[s] = en;//让en作为s出发的第一条边
}
int depth[maxn];//depth[i] 代表i点的深度
int f[maxn][25];//f[i][j]从i点向上跳2^j步会跳到哪里
void dfs(int now,int fa)//当前深搜到now点 now的父亲是fa
{
depth[now] = depth[fa] + 1;
f[now][0] = fa;
for (int i=1;i<=20;i++)
f[now][i] = f[f[now][i-1]][i-1];
for (int i=first[now];i!=0;i=ed[i].next)//枚举从now出发的所有边
if (ed[i].e != fa) dfs(ed[i].e,now);
}
int get_lca(int p1,int p2)//求p1 p2的lca
{//O(logn)
//第一步:调整p1 p2深度一样
if (depth[p1]<depth[p2]) swap(p1,p2);//把p1变成深度更深的点
for (int i=20;i>=0;i--)//尝试一次性跳2^i步 二进制拆分
if (depth[f[p1][i]] >= depth[p2]) //跳了2^i步之后 深度仍然>=depth[p2] 说明没有跳过
p1 = f[p1][i];
//第二步:求p1 p2 LCA
if (p1==p2) return p1;
for (int i=20;i>=0;i--)
if (f[p1][i] != f[p2][i])//让p1和p2一起跳了2^i步之后 仍然没有重合 说明没有跳过LCA
p1=f[p1][i],p2=f[p2][i];//p1 p2一起跳2^i步
return f[p1][0];
}
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int s,e,d;//这是一条从s到e 长度为d的边
cin >> s >> e;
add_edge(s,e);
add_edge(e,s);//如果是无向图
}
dfs(1,0);//假设根节点1
cin >>q;
for (int i=1;i<=q;i++)
{
int p1,p2;
cin >> p1 >> p2;
int p3=get_lca(p1,p2);
cout << depth[p1]-depth[p3] + depth[p2] - depth[p3] << endl;
}
}
最短路问题
\(floyd\):三维动态规划
#include<iostream>
#include<algorithm>
using namespace std;
int f[maxn][maxn][maxn];//f[i][j][k] 代表从j走到k中间经过的节点编号<=i的最短路径长度
//O(N^3)
//N 100
int main()
{
cin >> n >> m;
memset(f,0x3f,sizeof(f));//把f数组初始化为无穷大
//全部变成0x3f3f3f3f 0x:十六进制
for (int i=1;i<=n;i++)
f[0][i][i] = 0;
for (int i=1;i<=m;i++)
{
int p1,p2,d;
cin >> p1 >> p2 >> d;//从p1到p2长度为d的边
f[0][p1][p2] = min(f[0][p1][p2],d);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
f[i][j][k] = min(f[i-1][j][k] , f[i-1][j][i] + f[i-1][i][k]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cout << f[n][i][j] << endl;
}
#include<iostream>
#include<algorithm>
using namespace std;
int f[maxn][maxn];//f[i][j][k] 代表从j走到k中间经过的节点编号<=i的最短路径长度
int main()
{
cin >> n >> m;
memset(f,0x3f,sizeof(f));//把f数组初始化为无穷大
//全部变成0x3f3f3f3f 0x:十六进制
for (int i=1;i<=n;i++)
f[i][i] = 0;
for (int i=1;i<=m;i++)
{
int p1,p2,d;
cin >> p1 >> p2 >> d;//从p1到p2长度为d的边
f[p1][p2] = min(f[p1][p2],d);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
f[j][k] = min(f[j][k] , f[j][i] + f[i][k]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cout << f[i][j] << endl;
}
单源最短路:\(spfa\)
#include<iostream>
using namespace std;
const int maxn=100010;
const int maxm=200010;
int n,m,en,first[maxn];
//n代表点数
//m代表边数
//en代表当前已经插入几条边
//first[i] 代表从i点出发的第一条边的编号
struct edge
{
int e,d;//这条边的终点为e 长度为d
int next;//下一条边的编号为next
edge() {
e=d=next=0;
}
}ed[maxm];//ed[i]就代表编号为i的边
void add_edge(int s,int e,int d)//添加一条从s到e 长度为d的边
{
en++;//边的数量+1
ed[en].e = e;//记录新的这条边的终点
ed[en].d = d;//记录新的这条边的长度
ed[en].next = first[s];//新加的这条边的下一条边 应该是 原来从s出发的第一条边
first[s] = en;//让en作为s出发的第一条边
}
int dist[maxn];//dist[i]代表起点到i的最短路长度
queue<int> q;//用来存储可能改变其他点最短路的点
bool inque[maxn];//inque[i]代表i点当前是否在队列中
void spfa(int s)
//最坏情况下O(nm)
//随机情况下O(m)
{
memset(dist,0x3f,sizeof(dist));
dist[s]=0;//起点的最短路为0
q.push(s);
inque[s]=true;
while (q.size() != 0)//还有能够更改其他点最短路的点
{
int now=q.front();
q.pop();
inque[now] = false;
for (int i=first[now];i!=0;i=ed[i].next)//枚举所有从now出发的边
{
int j=ed[i].e;
int d=ed[i].d;//这是一条从now -> j长度为d的边
if (dist[now] + d < dist[j]) //说明了找到了一条到j的更短的路
{
dist[j] = dist[now]+d;
if (inque[j]==false) inque[j]=true,q.push(j);
}
}
}
}
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int s,e,d;//这是一条从s到e 长度为d的边
cin >> s >> e >> d;
add_edge(s,e,d);
add_edge(e,s,d);//如果是无向图
}
spfa(1);//计算从1号点到其他点的最短路
}
#include<iostream>
using namespace std;
const int maxn=100010;
const int maxm=200010;
int n,m,en,first[maxn];
//n代表点数
//m代表边数
//en代表当前已经插入几条边
//first[i] 代表从i点出发的第一条边的编号
struct edge
{
int e,d;//这条边的终点为e 长度为d
int next;//下一条边的编号为next
edge() {
e=d=next=0;
}
}ed[maxm];//ed[i]就代表编号为i的边
void add_edge(int s,int e,int d)//添加一条从s到e 长度为d的边
{
en++;//边的数量+1
ed[en].e = e;//记录新的这条边的终点
ed[en].d = d;//记录新的这条边的长度
ed[en].next = first[s];//新加的这条边的下一条边 应该是 原来从s出发的第一条边
first[s] = en;//让en作为s出发的第一条边
}
int dist[maxn];//dist[i]代表起点到i的最短路长度
bool use[maxn];//use[i]代表i点是否已经被选过了
priority_queue<pair<int,int> > heap;
//heap当中每个pair的first存储当前节点的dist值的相反数
//second存储当前节点的编号
void dijkstra(int s)
{//O((n+m)log(n+m))
memset(dist,0x3f,sizeof(dist));
dist[s]=0;
for (int i=1;i<=n;i++)
heap.push({-dist[i],i});//一开始把每个点扔到堆中
for (int j=1;j<=n;j++)//枚举n轮 每次选一个点
{
//选一个dist值最小 且没有被选过的点
while (use[heap.top().second] == true)//把被选过的堆顶扔掉
heap.pop();
int p = heap.top().second;//堆顶就是dist最小的点
heap.pop();
use[p]=true;//p点被选过了
//选出来的点是p
for (int i=first[p];i!=0;i=ed[i].next)//枚举从p出发的所有边 O(m)
{
int q=ed[i].e;
int d=ed[i].d;//是一条从p->q长度为d的边
if (dist[q] > dist[p] + d)
{
dist[q] = dist[p] + d;
heap.push({-dist[q],q});
}
}
}
}
int main()
{
cin >> n >> m;
for (int i=1;i<=m;i++)
{
int s,e,d;//这是一条从s到e 长度为d的边
cin >> s >> e >> d;
add_edge(s,e,d);
add_edge(e,s,d);//如果是无向图
}
dijkstra(1);//计算从1号点到其他点的最短路
}
\(END\)
钟长者再见!
标签:en,int,ed,DAY4,QBXT,edge,maxn,集训,first From: https://www.cnblogs.com/TianJiajun-chaqjs/p/18176044