PDF《介绍 0》

0

1 目录 介绍 First Chapter 图论

2 一些图论的模板总结 强连通分量 双联通分量 拓扑排序 割点和桥 2-SAT 最短路 Dijkstra 最短路 SPFA 最短路 Floyed 匈牙利算法 KM算法 LCA 最小生成树 Prim 最小生成树 Kruskal 最大流 Dinic 最小割 费用流 差分约束系统 图论

3 介绍 图论 1.

强连通分量 有向图强连通分量:在有向图中有一些点,这些点中如果能从A到B,那么一定从B 能到达A,这些点组成的点数最多的子图是原图的一个强连通分量. 运用场合:有 向图、有两两可达这种条件、往往通过把每个强连通分量缩点把原图化简成一棵树 模板代码: 图论

4 First Chapter void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock;

S.push(u);

for (int i = 0;

i < (int)G[u].size();

i++) { int v = G[u][i];

if (!pre[v]) { dfs(v);

if (lowlink[u] > lowlink[v]) lowlink[u] = lowlink[v];

else if (!sccno[v]) { if (lowlink[u] > pre[v]) lowlink[u] = pre[v];

} if (lowlink[u] == pre[u]) { scc_cnt++;

for(;

;

) { int x = S.top();

S.pop();

sccno[x] = scc_cnt;

if (x == u) break;

} } void find_scc(int n) { dfs_clock = scc_cnt = 0;

MEM(sccno);

MEM(pre);

MEM(ans);

for (int i = 1;

i B->C->D->E->A这样A,B,C,D,E就是同一个集合,如 果还有C->F->C,那么F也属于上面那个集合,所以这题就是求点数大于2的强连通 分量的个数. 大白书的模板(Tarjan)中用了一个sccno[]数组,sccno[i]记录第i个点所属的强连 通分量号然后我们只需要用一个cnt[]数组,记录每个块中点的个数,如果cnt[i] > 1,说明第i个块是符合条件的,答案数目加1,最后输出答案数. #include #include #include #include using namespace std;

#define MEM(a) memset(a, 0, sizeof(a)) const int maxv = 21000;

vectorG[maxv];

int pre[maxv], lowlink[maxv], sccno[maxv], ans[maxv], dfs_clock, sc stackS;

void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock;

S.push(u);

for (int i = 0;

i < (int)G[u].size();

i++) { int v = G[u][i];

if (!pre[v]) { dfs(v);

if (lowlink[u] > lowlink[v]) lowlink[u] = lowlink[v];

else if (!sccno[v]) { if (lowlink[u] > pre[v]) lowlink[u] = pre[v];

} if (lowlink[u] == pre[u]) { scc_cnt++;

for(;

;

) { int x = S.top();

S.pop();

sccno[x] = scc_cnt;

图论

6 First Chapter if (x == u) break;

} } void find_scc(int n) { dfs_clock = scc_cnt = 0;

MEM(sccno);

MEM(pre);

MEM(ans);

for (int i = 1;

i rhs.c + dist[rhs.v];

} };

struct Edge { int v, cost;

Edge (int _v = 0, int _cost = 0) : v(_v), cost(_cost) {} };

图论

37 First Chapter vectorE[maxn], revE[maxn];

void Dijkstra(int n, int s) { memset(vis, false, sizeof(vis));

for (int i = 1;

i dist[u] + cost) { dist[v] = dist[u] + cost;

que.push(Node(v, dist[v]));

} } int astar(int s) { priority_queue que;

que.push(Node(s, 0));

k--;

while (!que.empty()) { Node pre = que.top();

que.pop();

int u = pre.v;

if (u == t) { if (k) k--;

else return pre.c;

for (int i = 0;

i < (int)revE[u].size();

i++) { 图论

38 First Chapter int v = revE[u][i].v;

int c = revE[u][i].cost;

que.push(Node(v, pre.c + c));

} return -1;

} void addedge(int u, int v, int w) { revE[u].push_back(Edge(v, w));

E[v].push_back(Edge(u, w));

} int main() { //freopen("in.txt", "r", stdin);