图和最短路

图

邻接矩阵

优化的邻接矩阵

使用变长数组，用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

Clang8