【题意】:给出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, -1sizeof(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, 00);
 30 }
 31 
 32 int isap(int s, int t, int n) {
 33     int u, v, now;
 34     memset(dist, 0sizeof(dist));
 35     memset(low, 0sizeof(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] + 1break;
 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]] == 0break;
 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 }