coder370的博客

kosaraju算法求联通图个数 例题：hdu1269（求整个图是否联通 -> 只有一个连通图） #include <cstdio> #include <vector> #include <cstring> using namespace std ; const int N = 10005 ; vector<int> from[N] , t...

假设n为图的点，m为连接的边，若m远小于n*n的图称为稀疏图，而m相对较大的图称为稠密图。稀疏图适合用vector数组保存，还有最近比较流行的邻连接表保存。在这种表示法中，每个结点i都有一个链表，里面保存着从i出发的所有边，对于无向图来说，每条边会在连接表中出现两次。 Floyd算法： 求出每两点之间的最短路，关键代码： 在这之前要先初始化，d[i][i] = 0 ,其他d为无穷大INF，注意I...

最小生成树 设G（V，E）是无向；联通带权图，对图中每一条边（u，v）的权威c[u][v] ， 表示联通u与v的代价，如果G的子图T是一颗包含G的所有顶点的树，则称T为G的生成树，生成树上的权总和成为该生成树的耗费，在G的所有生成树中耗费最小的生成树成为G的最小生成树。 krukskal算法 算法实现：首先将G的n个顶点看成是n个孤立的连通分量，将所有边的权值从小到大排序，然后从第一条边开始，依...

p1330 封锁阳光 题意是每个点要分隔开但是取走的点不能相邻，转化为染色就是相邻的点不能为同种颜色。 做法：遍历未染色的点，将未染色的点染为黑色，相邻的点染为白色，依次类推，要注意每次dfs是当前的联通图，取断点要去当前的最小值，所以在开始遍历那里之前，颜色数量要清0。 #include <cstdio> #include <vector> #include <...

输入a和b，a的vector数组里添加b，且b的进度加1，输入结束后，遍历map看哪一个的进度为0则为进栈，然后若栈不为空则继续循环和弹出，比如a进度为0则出栈，然后a中的vector数组中的每一个节点的进度减一，在判断这些节点的进度是否为0，若是则进栈。 #include <iostream> #include <map> #include <string>...

floyd算法（hdu2544） #include <cstdio> const int N = 105 ; const int INF = 1e6 ; //路口间的初始距离，看成无穷大，相当于断开 int graph[N][N] ; int n , m ; void floyd(){ int s = 1 ; for (int k = 1 ; k <= n ...