【题意】：给出n个点，和n*n的矩阵表示有向图。maz[i][j]为-1表示i到j没有路径；不为-1则表示i到j的路径长度。给出一个s和t，要求s到t的没有公共边的最短路有多少条？如果s和t重合输出inf。
【题解】：先预处理s到各点的最短路和t到各点的最短路，这里可以用dij对正图和反图求最短路；或者用floyd直接求点到点的最短路。
这里有个trick，用floyd时必须初始化自己到自己的距离为零，虽然sample的输入都是零，但后面的case居然不是，就这个原因我wa了一个小时有多，感叹出题人太无聊了。
求完最短路，设maz[i][j]表示i到j的最短路，map[i][j]表示i到j的直接距离，然后对原图枚举每一条边e(i,j)，如果e(i,j)满足maz[s][i]+map[i][j]+maz[j][t]==maz[s][t]。
则说明e(i,j)必定是最短路的一部分，于是连边i->j，容量为1，表示只能用一次。最后求s到t的最大流，就是没有公共边的最短路的条数。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 105
6 #define maxm 100005
7 const int INF = 99999999;
8 int s, t;
9 int n, m;
10 int dist[maxn], low[maxn], tot, eh[maxn], pre[maxn], cnt[maxn], cur[maxn];
11 int maz[maxn][maxn], map[maxn][maxn];
12
13 struct Edge {
14 int u, v, cap, flow, next;
15 }et[maxm];
16
17 void init() {
18 tot = 0;
19 memset(eh, -1, sizeof(eh));
20 }
21
22 void add(int u, int v, int cap, int flow) {
23 Edge E = {u, v, cap, flow, eh[u]};
24 et[tot] = E;
25 eh[u] = tot++;
26 }
27
28 void addedge(int u, int v, int cap) {
29 add(u, v, cap, 0), add(v, u, 0, 0);
30 }
31
32 int isap(int s, int t, int n) {
33 int u, v, now;
34 memset(dist, 0, sizeof(dist));
35 memset(low, 0, sizeof(low));
36 for(u = 0; u <= n; u++) cur[u] = eh[u];
37 int maxflow = 0;
38 u = s;
39 low[s] = INF, cnt[0] = n;
40 while(dist[s] < n) {
41 for(now = cur[u]; now != -1; now = et[now].next)
42 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
43 if(now != -1) {
44 cur[u] = pre[v] = now;
45 low[v] = min(low[u], et[now].cap - et[now].flow);
46 u = v;
47 if(u == t) {
48 for(; u != s; u = et[pre[u]].u) {
49 et[pre[u]].flow += low[t];
50 et[pre[u]^1].flow -= low[t];
51 }
52 low[s] = INF;
53 maxflow += low[t];
54 }
55 } else {
56 if(--cnt[dist[u]] == 0) break;
57 dist[u] = n;
58 cur[u] = eh[u];
59 for(now = eh[u]; now != -1; now = et[now].next)
60 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
61 dist[u] = dist[et[now].v] + 1;
62 cnt[dist[u]]++;
63 if(u != s) u =et[pre[u]].u;
64 }
65 }
66 return maxflow;
67 }
68
69 void floyd() {
70 for(int k = 0; k < n; k++)
71 for(int i = 0; i < n; i++)
72 if(maz[i][k] != -1)
73 for(int j = 0; j < n; j++)
74 if(maz[k][j] != -1)
75 if(maz[i][j] == -1) maz[i][j] = maz[i][k] + maz[k][j];
76 else maz[i][j] = min(maz[i][j], maz[i][k] + maz[k][j]);
77 }
78
79 void build() {
80 init();
81 for(int i = 0; i < n; i++)
82 if(maz[s][i] != -1)
83 for(int j = 0; j < n; j++)
84 if(maz[j][t] != -1)
85 if(i != j && map[i][j] != -1 && maz[s][i] + map[i][j] + maz[j][t] == maz[s][t])
86 addedge(i, j, 1);
87 }
88
89 int main() {
90 while(cin >> n) {
91 for(int i = 0; i < n; i++) {
92 for(int j = 0; j < n; j++) {
93 cin >> maz[i][j];
94 if(i == j) maz[i][j] = 0; //没有这句就wa,不知道什么原因,是输入的时候不保证 maz[i][i] == 0 ???
95 map[i][j] = maz[i][j];
96 }
97 }
98 cin >> s >> t;
99 if(s == t)
100 cout << "inf" << endl;
101 else {
102 floyd();
103 build();
104 cout << isap(s, t, n) << endl;
105 }
106 }
107 return 0;
108 }