开始学图论辣
图的基本模型
图是点和边组成的集合体，G = <V, E>
v是点集，e是边集
还有就是有向图无向图啥的
算了太水了不写了
提几个没大见过的吧
环
环上任意两点间可以随意到达，自环就是一个点有一条连向自己的道路
路径
其实就是u-v的一条路，如果路径上的各顶点均不互相重复，称这样的路径为简单路径
特殊的图
树上两点之间路径是唯一的，而且树一定有n个点n-1条边，保证所有点之间都可互相到达（无向图）
完全图指n个点之间任意两个点之间都有一条边（无向图）
竞赛图是完全图上的每一个边都随便定一个方向
基环树是说一个环上出去的点全是树
如果一条边只属于一个环，那么叫做仙人掌
图的输入方式
最常见的输入方式是用 1 − N 表示顶点，并逐行给出 M 条边所连接的两点和边权大小。
N M
u1 v1 w1
u2 v2 w2
. . .
um vm wm
如果有点权，一般会用一行 N 个数表示每个点的权值大小。
p1 p2 . . . pn
poj经常会给一些智障图的出法，比如告诉你一个点的出度是x，然后紧接着x个数表示u-vi有一条边。。。
还有一个变态输入方式
输入文件的第一行为n （n<=1000），表示火星上基地的数目。接下来的n-1行每行有一个正整数，其中文件第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有a[i]<i。
图的遍历方法
DFS和BFS
三种dfs序（在书上的）遍历方式
前序 中序 后序
例一
给定一个有向图，边权为 1 或 2，求单源最短路。
不能用任何最短路算法；
稍微改写一下 BFS 即可。
创建三个集合， Q0表示当前层， Q1 表示距离为 1 的层，Q2 表示距离为 2 的层，初始 Q0 = {s}, Q1 = ∅, Q2 = ∅
依次取出 Q0 中的点，将其邻点放入对应的 Q1 或 Q2 中
Q0 = Q1, Q1 = Q2, Q2 = ∅
注意一个点可能和当前层既有长度为 1 的边，又有长度为 2 的
边，应当将其加入 Q1 而非 Q2
例二
给出一个有向图和起点 s，对每条边 < u, v > 回答，如果删去这条边，从 s 到 v 的最短路长度是否会改变。
题解
求出从 s 出发的单源最短路
建立最短路图，即保留满足 dv du + 1 的边 < u, v >
在最短路图上，如果 v 的入度为 1，则该入边是从 s 到 v的必经边，若删去则 v 的最短路长度会改变
在最短路图上，如果 v 的入度大于 1，则删去任何一条入边， v 的最短路长度都不会改变
拓扑排序
有向无环图的拓扑排序即将所有顶点排为线性序列，使得对于任意的 < u, v >∈ E，都有 u 在线性序列中出现于 v 之前。
有向图中如果有环，则一定不存在拓扑排序；如果没有环，则一定存在拓扑排序。
选取一个入度为 0 的点记为 u
将 u 添加到线性序列末端
删去所有 u 的出边（如果有某个点入度为0，那么把他加进去）
重复上述步骤直到所有点都被加入序列
代码
void toposort()
{
queue<int> q;
for (int i = 1; i <= n; ++i)
if (in[i] == 0) //入度为0
q.push(i);
while (!q.empty())
{
int temp = q.front();
q.pop();
for (int i = head[temp]; i; i = edge[i].next)
{
int v = edge[i].to;
if (--in[v] == 0)
q.push(v);
}
}
}
例一（裸题）
有 n 项任务，有 m 个限制，第 i 个限制要求执行任务 ui 之前必须要完成任务 vi。请问是否存在合适的任务执行顺序，满足所有的限制。
实际上是u->v;
将每个任务视为一个点，任务之间的依赖构成了有向边。如果该有向图中没有环，则存在拓扑排序，而拓扑排序就是可行的任务执行顺序；如果该有向图中存在环，则无解。
注意如果长度不是n那么有环无解
bzoj 道路和航线
FJ 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 T 个城镇 (1 ≤ T ≤ 25000)，编号为 1 到 T。这些城镇之间通过 R 条道路 (1 ≤ R ≤ 50000) 和 P 条航线(1 ≤ P ≤ 50000) 连接。每条道路 i 或者航线i 连接城镇 Ai 到Bi，花费为 Ci。
对于道路， 0 ≤ Ci ≤ 10000; 然而航线的花费很神奇，花费 Ci 可能是负数 (−10000 ≤ Ci ≤ 10000)。道路是双向
的，可以从 Ai 到 Bi，也可以从 Bi 到 Ai，花费都是 Ci。然而航线与之不同，只可以从 Ai 到 Bi。事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：如果有一条航线可
以从 Ai 到 Bi，那么保证不可能通过一些道路和航线从 Bi 回到
Ai。由于 FJ 的奶牛世界公认〸分给力，他需要运送奶牛到每一
个城镇。他想找到从发送中心城镇 S 把奶牛送到每个城镇的最
便宜的方案，或者知道这是不可能的。
有向边一定不在环中
注意到如果有一条航线可以从 Ai 到 Bi，那么保证不可能通过一
些道路和航线从 Bi 回到 Ai。
换言之，不存在包含航线（负权单向边）的环。
首先加入所有正权无向边，找出所有连通块，每个连通块缩为一
个点。再加入所有单向边，此时图一定为 DAG。
在 DAG 上用 BFS 更新最短路，在正权无向边组成的连通块
（缩点）内部使用 Dijkstra 更新最短路。
最短路
floyd
很水很水 基于DP，我们只需要枚举断点k就可以
void floyd()
{
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
时间复杂度 O(N^3)
空间复杂度 O(N^2)
Dijkstra
速度最快的最短路算法，但是只适用于没有负权边的图
将所有点分为两个集合，最短路确定的集合 S 和最短路未确定的集合 T，初始 S = {s}
求 T 中每个点 v 的当前最短路
dv = min<u, v> ∈E, u∈S{D_u + W_u, v}
取出 T 中 dv 最小的点，其最短路一定就是 dv，将其加入 S(就是这个地方比较慢)
不断重复上面的操作，直到所有点的最短路径都确定
朴素写法时间复杂度较劣，可以采用堆优化至 O((N + M)logN)
SPFA
Bellman-Ford 我就直接跳过了吧，SPFA其实就是队列优化的Bellman-Ford
从初始点开始找他所有的出边，如果某个点的距离被更新了，那么我们把这个点放到队列当中去，并且一直这么写。
void spfa()
{
for (int i = 1; i <= n; ++i)
{
dis[i] = inf;
vis[i] = 0;
}
dis[s] = 0;
vis[s] = 1;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop(), vis[u] = 0;
for (int i = head[u]; i; i = edge[i].next) //
{
int v = edge[i].to;
if (dis[v] > dis[u] + edge[i].dis)
{
dis[v] = dis[u] + edge[i].dis;
if (!vis[v])
{
q.push(v);
vis[v] = 1;
}
}
}
}
}