ZOJ 2760 How Many Shortest Path

暑假集训第一天，早上看了一下支配树，结果表示完全不会，看不懂……不得不回老本写起了网络流

题意：
给你一个距离矩阵，问你完全不重叠的最短路数目。

思路：
完全不重叠，意为每条边只能走一次，我以网络流建模，对于每条在最短路径内的边的流量设置为1，跑出来的结果即题意所求。这个很自然想得到吧
关键就在于如何判断一条边是否属于最短路径。
这里给出一种比较好的方法，对于一条边 ( u , v ) ，如果 min ( st , u ) + ( u,v ) + min ( v , en ) 等于最短路径长度，那么这条边就属于最短路径 这也是很显然的

注： 如果起点与终点相同，则直接输出inf ，本人英语不好，看了一下题意我还意淫成了 如果存在( st , en ) 就输出inf。
结果我tle了4发……
因为一直wa我看了一下其他题解，居然有人以自环>=0为理由A不了……我感觉很奇怪。如果自环权值非负，那么正权值自环必定不在最短路径中，而零自环加不加都没有任何影响。

其他的就是代码美丑的问题了。

AC code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;

int n, idx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn];
int mat[maxn][maxn];
int diss[maxn], dist[maxn], cpmat[maxn][maxn];

struct node {
    int flow;
    int to;
    int nxt;
} edges[4 * maxn * maxn];

void addEdge(int u, int v, int f)
{
    edges[idx].to = v;
    edges[idx].flow = f;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u;
    while (l < r) {
        u = que[l++];
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que[r++] = v;
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void spfa(int s, int* dis, int sp[maxn][maxn])
{
    bool vis[maxn];
    int que[maxn];
    memset(vis, false, sizeof vis);
    for (int i = 0; i <= n; i++)
        dis[i] = inf;
    dis[s] = 0;
    vis[s] = true;
    int l = 0, r = 1;
    que[0] = s;
    while (l < r) {
        int u = que[l++];
        vis[u] = 0;
        for (int v = 1; v <= n; v++) {
            if (dis[v] > dis[u] + sp[u][v]) {
                dis[v] = dis[u] + sp[u][v];
                if (!vis[v]) {
                    vis[v] = 1;
                    que[r++] = v;
                }
            }
        }
    }
}

bool createGraph()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cpmat[i][j] = mat[j][i];
    memset(head, -1, sizeof head);
    idx = 0;
    st++, en++;
    spfa(st, diss, mat);
    spfa(en, dist, cpmat);
    //printf("dist --> %d %d %d %d\n", dist[1], dist[2], dist[3], dist[4]);
    int min_len = diss[en];
    if (min_len == inf)
        return false;
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++) {
            if (diss[u] + mat[u][v] + dist[v] == min_len) {
                //printf("%d %d %d %d %d\n", diss[u], mat[u][v], dist[v], u, v);
                addEdge(u, v, 1);
                addEdge(v, u, 0);
            }
        }
    return true;
}

int main()
{
    int len;
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                scanf("%d", &len);
                mat[i][j] = len < 0 ? inf : len;
            }
        scanf("%d %d", &st, &en);
        if (st == en) {
            puts("inf");
            continue;
        }
        if (createGraph())
            printf("%d\n", dinic());
        else
            puts("0");
    }
    return 0;
}