【題意】：給出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 }