最小生成树
最小生成树理论基础：
1.任意一颗最小生成树一定可以包含无向图中权值最小的边
2.给定一张无向图G=(V, E)，n=|M|, m=|E|。从E中选出k < n- 1条边构成G的一个生成森林。若再从剩余的m-k条边中选n- 1 - k条边添加到生成森林中，使其成为G的生成树，并且选出的边的权值之和最小。则该生成树一定可以包含m - k条边中连接生成森林的两个不连通节点的权值最小的边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 最小生成树{
Prim algorithm{
1.朴素版Prim O(O^2) 稠密图{
将所有点初始化为正无穷
迭代n次
找到集合外最近的点
判断这个点是不是连通的
如果不是第一条边就进行累加
用这个点更新集合外的点到集合的距离(不更新累加距离，只更新最短距离)
标记这个集合并加入集合
}
2.堆优化Prim O(mlogn) 稀疏图{
这里就先不写了...
}
} Kruskal algorithm{ O(mlogm) 稀疏图
1.将所有边按权重从小到大排序 O(mlogm)
2.初始化并查集
3.从小到大枚举每条边(a-b权重c),若a,b不连通，将a,b加入集合中
}
}
|
二分图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 二分图{
1.染色法{ O(n+m)
1.建邻接表
2.for(1~n)
if(i未染色）
dfs(i)
需要标记每个点是否被染色
}
2.匈牙利算法{ O(nm),实际运行时间远小于O(nm)
最快时间内得出二分图成功匹配的最大的数量（成功匹配：没有两条边共用一个点）
}
最大流算法
}
|
最小生成树
Prim algorithm
prim算法是从一个点开始扩展，逐渐得到一棵树
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
| #define MAXN 510
#define INF 0x3f3f3f3f
int n,m;
int g[MAXN][MAXN],dis[MAXN];
bool st[MAXN];
int prim(){
memset(dis,0x3f,sizeof(dis));
int res=0;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dis[t]>dis[j]))
t=j;
if(i!=1&&dis[t]==INF) return INF;
if(i!=1) res+=dis[t];
for(int j=1;j<=n;j++)
dis[j]=min(dis[j],g[t][j]);
st[t]=true;
}
return res;
}
|
Kruskal算法
结合了并查集的思想，将所有边排序后开始选择，在图中主键连通的过程
1
2
3
4
5
6
| Kruskal algorithm{ O(mlogm) 稀疏图
1.将所有边按权重从小到大排序 O(mlogm)
2.初始化并查集
3.从小到大枚举每条边(a-b权重c),若a,b不连通，将a,b加入集合中
}
}
|
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
| int n,m;
int fa[MAXN];
struct Edges{
int a,b,w;
bool operator < (const Edges W) const{
return w<W.w;
}
} edges[MAXN];
int find(int x){
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&edges[i].a,&edges[i].b,&edges[i].w);
}
sort(edges+1,edges+1+m);
for(int i=1;i<=m;i++) fa[i]=i;
int res=0;
int cnt=0;
for(int i=1;i<=m;i++){
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
a=find(a),b=find(b);
if(a!=b){
res+=w;
cnt++;
fa[a]=b;
}
}
if(cnt<n-1) puts("impossible");
else printf("%d\n",res);
return 0;
}
|