图和最短路
图
邻接矩阵
优化的邻接矩阵
使用变长数组，用edge[i][j]表示从i点连出的第j条边
使用cnt表示从i连出的边有多少
邻接表
void addedge(int x, int y, int z) {
tot++;
pre[tot] = last[x];
last[x] = tot;
other[tot] = y;
val[tot] = z;
}
度：
对于每一个点，进入该点的边的数量和离开该点的边数量，分别称为入度和出度。
最短路算法
SPFA：
使用IN数组进行BFS的常数优化，即，保证了同一个点不会重复入队。
dijkstra
不能处理有负边权的图
void dijkstra(int st, int ed) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
heap_push(st, 0);
while (!heap_empty()) {
int u = heap_top();
heap_pop();
if (vis[u]) continue;
vis[u] = 1;
for (int p = last[u]; p; p = pre[p]) {
int v = other[p];
int cost = val[p];
if (!vis[v] && dis[v] > dis[u] + cost) {
dis[v] = dis[u] + cost;
heap_push(v, dis[v]);
}
}
}
}
多源最短路
floyd：
注意k是最外层
floyd最初的作用是用来传递闭包
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i == j) f[i][j] = 0;
else f[i][j] = inf;
}
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]);
}
判负环
使用floyd，如果某个点的f[i][i] < 0，那么可知有过该点的负环
使用SPFA：使用cnt数组，表示某个点入队的次数，如果cnt[i] > n 那么存在负环
使用DFS判负环：？
http://codeforces.com/gym/101873/problem/C
http://www.cnblogs.com/orangee/p/9644216.html
例题1
