题意：给定n个点m条边。要使任意两个点可以通过两条严格不同的路径到达。即边不能重复，点可以重复。求需要添加的最小边数 题目就是要求使这个图成为边双连通分量所需添加的最小边数。 我的做法： 将边双连通分量相关的点缩点。然后求出度为1的个数=num。答案就是(num+1)/2或者说是num/2+num%2 理由：度为1的肯定是叶子节点或者根节点。将叶子节点两两配对。如果是奇数的话就任意与一个节点配对成边即可。 我在做边双连通分量缩点的过程异常麻烦。 首先我求出桥，然后删掉这些桥。将连通块缩点(这些连通块是边双连通分量)。然后再计算度数。。写的很多。感觉很麻烦。肯定有更简短的代码。。 ---------2014/7/11 在下面还有一个代码 修改过后的。。写法比前面这个简便多了。 //author: CHC//First Edit Time: 2014-07-11 10:04//Last Edit Time: 2014-07-11 11:53#include <iostream>#include <cstdio>#include <cstring>#in ...

这道题的输入异常鬼畜。= =无法直视 题意：给一个图。输出割点以及删掉割点后形成几个连通块 还是忍不住吐槽：异常鬼畜的输入，还有输出，一不注意就PE 还有，注意到这道题的点不是按顺序给定你的。你需要建立一个point数组来存储点。代码如下。= = 套个模板一不小心就WA了。鬼畜的题、 //author: CHC//First Edit Time: 2014-07-07 21:33//Last Edit Time: 2014-07-07 21:33#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>using namespace std;#define MAXN 1010vector <i ...

题意： 给n个点m条有向边。求出满足这个条件的最小集合数量：该集合内任意两个点相互之间不能直接或间接到达。也就是说 这个集合内的任意两个点都没有关系。 输出满足这个条件的最小集合数 思路： 首先将强连通分量缩点。该缩点的点权为点的个数。因为强连通分量中任意两个点都有直接或者间接关系。 缩点后重新建图。 然后对新图拓扑排序求最长链。 拓扑排序的三个步骤(队列实现)： 1)将入度为0的点放入队列中 2)从队列中取出点，将其边指向的下一个点的入度-1 3)重复1)、2)的步骤直到队列为空 //author: CHC//First Edit Time: 2014-07-07 15:27//Last Edit Time: 2014-07-07 15:27#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <que ...

这题做的好艰辛。。 先说题意： 给n个点 m条边 m条边中有单向边或双向边。题目保证给定的边一定构成一个连通图。 现在要求 尽可能多的重定向双向边为单向边。使图最后的结果为强连通图。输出所有双向边的情况（定向或者没定向的都要输出) 思路： 1.首先看哪些边一定不能重定向（就是原样输出的那些无向边）。先把所有的边看成无向边，求桥(tarjan)。把这些桥原样输出(这些桥一定是无向边，题目保证了图是连通的)(为什么桥不能重定向。因为重定向后图就不连通了)。 2.这些桥把许多个连通块连通起来。我们删掉这些桥。对这些连通块内部的无向边进行重定向 3.重定向边。参考tarjan算法。建立一颗dfs树。 1)如果无向边是树边。 如果u能到达u的祖先，也就是dfn[u]>=low[u]，说明这条边是正确的 直接输出 u v 1。 如果u不能到达u的祖先，dfn[u]<low[u]，说明这条边需要反向 输出 v u 1 2)如果无向边是回边。 说明方向是对的，因为借助这条边可以回到祖先。直接输出u v 1 这题做的好艰辛。。vector建图MLE 邻接矩阵建图MLE 邻接表才是真爱。AC ...

本题的题意为 给n个点m条单向边 然后再给出0~n个点的点权（有正有负） 要求是 从某一点开始走，走到一个点：可以选择进去，获得点权（只能进一次）或者选择绕过这个点继续走，求能获得的最大权值 我的做法：强连通缩点+bfs //author: CHC//First Edit Time: 2014-06-13 20:26//Last Edit Time: 2014-06-13 20:26#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>using namespace std;#define TMAXN 30010vector <int> e[TMAXN];vector <int ...

本题题意为：给你n个点m条单向边。 询问这个图是否是符合这个条件的：任意选两个点 u v 、 u可以到达v或者v可以到达u。 如果是的话就输出Yes，否则输出No 传说中的弱连通。 我的做法： 先 强连通缩点 再选一个入度为0的点开始跑一条边的bfs。最后如果所有的点都被标记过那么就是 否则就不是 //author: CHC//First Edit Time: 2014-06-10 22:09//Filename:D:\bc\做题\图论训练\强连通\poj 2762 Going from u to v or from v to u\1.cpp#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm> ...

这道题的题意为： 给你一个nm的地图 这个地图中有三种格式  第一种 '’ 代表这个地方可以使用魔法跳转到另一个地方（后面告诉）。 第二种 ‘0’~‘9’ 代表这个地方可以得到的矿石数量。 第三种 ‘#’   代表这个地方是墙 不能通过。 然后再给你每一个’*'可以跳转到的地方 从左到右 从上到下 一次给出 起点为 左上角 每一个方格 可以向下或者向右走  然后让你求 这个地图中 最多能得到多少矿石（起点为左上角，终点任意）（魔法可以无限次用 但是 每个方格的矿石只能得到一次） 输出这个答案。 我的做法： spfa+缩点 缩点可以用tarjan强连通算法。 如果可以施展魔法跳到另一个的地方之后。 如果能从那个地方再回到这个地方。那么所有这条路径上的点权都可以缩为1点。它形成了一个环 可以通过tarjan求出强连通分量 然后以这些强连通分量建图跑一遍spfa就可以得出答案。。详情代码。 //author: CHC//First Edit Time: 2014-06-10 19:33//Filename:D:\bc\做题\图论训练\强连通\poj 3592 Instantaneous T ...

这道题的题意为：给你一个nxn的矩阵 分别代表 i到j 的距离，再给q条无向边，求使任意两个点能互相到达的最小距离 我的做法 ：强连通缩点+最小生成树 //其实这题只用最小生成树可以做的 为了练习强连通而。。 1A 15MS //author: CHC//First Edit Time: 2014-05-29 21:16//Last Edit Time: 2014-05-30 11:12//Filename:1.cpp#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>using namespace std;#define MAXN 110#define DIS_INF 10000 ...

中文题  问任意两点是否能到达 问的就是 这个图是否为强连通分量 1A #include <iostream>#include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std;#define MAXN 10010int low[MAXN],dfn[MAXN],stack[MAXN],sum[0],top,times,m,n;bool instack[MAXN];vector <int> e[MAXN];void tarjan(int u){ dfn[u]=low[u]=++times; stack[top++]=u; instack[u]=true; for(int i=0;i<(int)e[u].size();i++){ int v=e[u][i]; if(!dfn[v]){ tarja ...

本题中文题 题意很明显  问最少要打几个电话  我的做法是强连通+缩点 1A #include <iostream>#include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std;#define MAXN 1010int stack[MAXN],low[MAXN],dfn[MAXN],sum[MAXN],tran[MAXN],times,top,m,n;bool instack[MAXN];int ru[MAXN];vector <int> e[MAXN];void tarjan(int u){ low[u]=dfn[u]=++times; stack[top++]=u; instack[u]=true; for(int i=0;i<(int)e[u].size();i++){ int v=e[u][i]; if(!d ...