大大大芒果

图论

学习笔记(11) 数学知识(3) 赛后总结(15)

/ 注册

全部文章 / 图论（共16篇）

POJ1639 Picnic Planning

题目链接：https://ac.nowcoder.com/acm/contest/1056/B书P368 ①：Kruskal算法https://blog.nowcoder.net/n/012b92baab1f4ee59bb17b9bcb8dadb4本题中用这个算法求去掉根节点1后的最小生成树 ②贪心...

2020-10-15

0 579

CH6201 走廊泼水节

题目地址：https://ac.nowcoder.com/acm/contest/1056/A思路：n个节点的树有n条边，先把边从小到大排序，依次扫描每一条边。如果是一条边，那么就不需要加边如果是二条边，需要加一条边，这条边的权值应该是当前边的权值+1，如果加边的权值相同，最小生成树就不唯一如果是三...

2020-10-12

0 513

最小生成树

①Kuskal算法（克鲁斯卡尔）时间复杂度为O(m log m) #include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; struct edge { int u,v,w; }; edge a[maxn];...

2020-10-12

1 584

从点S到E刚好经过N条边的最短路径

题目地址：https://ac.nowcoder.com/acm/contest/1055/G《算法进阶》P362 ①关于min的矩阵乘法：https://blog.nowcoder.net/n/09c63cb41aba4ab5bf67450b243e0eba若矩阵保存任意两点之间恰好经过m条边的...

2020-10-12

0 451

用floyd找最小环

#include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; const int maxn=300+10; int a[maxn][maxn],d[maxn][maxn],pos[maxn][maxn];//...

2020-10-12

1 470

用floyd求传递闭包

#include<bits/stdc++.h> using namespace std; const int maxn=26+1; int n,m; int a[maxn][maxn],b[maxn][maxn]; int floyd() { memcpy(b,a,sizeof(...

2020-10-12

0 542