How Many Shortest Path

题目：

给出一张图，求解最短路有几条。处理特别BT。还有就是要特别处理map[i][i] = 0，数据有不等于0的情况！

竟然脑残到了些错floyd！

！。！！

！

14次wrong。！

！。。！

。。

算法：

先最短路处理，把在最短路上的边加入上。既是。dist[s][i] + map[i][j] == dist[s][j]表示从起点到i点加上当前边是最短路。把这个加入到网络流边集中。容量为1.然后，建立一个超级源点。容量为INF。

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdio>

#include <cstring>

using namespace std;

const int INF = 1 << 30;

const int MAXN = 200 + 10;

struct Edge{

   int from,to,cap,flow;

   Edge(){};

   Edge(int _from,int _to,int _cap,int _flow)

      :from(_from),to(_to),cap(_cap),flow(_flow){};

};

vector<Edge> edges;

vector<int> G[MAXN];

int cur[MAXN],d[MAXN];

bool vst[MAXN];

int N,M,src,sink;

int mat[MAXN][MAXN],dist[MAXN][MAXN];

int ss,tt;

void init(){

    for(int i = 0;i <= N+5;++i)

        G[i].clear();

    edges.clear();

}

void addEdge(int from,int to,int cap){

   edges.push_back(Edge(from,to,cap,0));

   edges.push_back(Edge(to,from,0,0));

   int sz = edges.size();

   G[from].push_back(sz - 2);

   G[to].push_back(sz - 1);

}

void flody(){

    memcpy(dist,mat,sizeof(mat));

    for(int i = 0;i < N;++i)

        for(int j = 0;j < N;++j)

           dist[i][j] = (dist[i][j]==-1?

INF:dist[i][j]);

    for(int k = 0;k < N;++k)

        for(int i = 0;i < N;++i)

           for(int j = 0;j < N;++j){

//             if(dist[i][k] == INF||dist[k][j] == INF) continue;

             if(dist[i][k] < INF && dist[k][j] < INF&&dist[i][j] > dist[i][k] + dist[k][j])

                dist[i][j] = dist[i][k] + dist[k][j];

           }

}

bool BFS(){

    memset(vst,0,sizeof(vst));

    queue<int> Q;

    Q.push(src);

    d[src] = 0;

    vst[src] = 1;

    while(!Q.empty()){

        int u = Q.front(); Q.pop();

        for(int i = 0;i < (int)G[u].size();++i){

            Edge& e = edges[G[u][i]];

            if(!vst[e.to] && e.cap > e.flow){

                vst[e.to] = 1;

                d[e.to] = d[u] + 1;

                Q.push(e.to);

            }

        }

    }

    return vst[sink];

}

int DFS(int x,int a){

   if(x == sink || a == 0)

     return a;

   int flow = 0,f;

   for(int& i = cur[x];i < (int)G[x].size();++i){

       Edge& e = edges[G[x][i]];

       if(d[e.to] == d[x] + 1 && (f = DFS(e.to,min(a,e.cap - e.flow))) > 0){

            e.flow += f;

            edges[G[x][i]^1].flow -= f;

            flow += f;

            a -= f;

            if(a == 0) break;

       }

   }

   return flow;

}

int maxFlow(){

   int flow = 0;

   while(BFS()){

       memset(cur,0,sizeof(cur));

       flow += DFS(src,INF);

   }

   return flow;

}

int main()

{

//   freopen("Input.txt","r",stdin);

    while(~scanf("%d",&N)){

         init();

         for(int i = 0;i < N;++i)

            for(int j = 0;j < N;++j){

               scanf("%d",&mat[i][j]);

            }

         for(int i = 0;i < N;++i)

           mat[i][i] = 0;

         scanf("%d%d",&ss,&tt);

         flody();

         if(ss == tt){

            printf("inf\n");

            continue;

         }

         src = N + 2; sink = tt;

         addEdge(src,ss,INF);

         // 建图

         for(int i = 0;i < N;++i){

            if(dist[ss][i] == INF) continue;

            for(int j = 0;j < N;++j){

                if(i == j) continue;

                if(dist[ss][j] == INF||mat[i][j] == -1) continue;

                if(dist[ss][i] + mat[i][j] == dist[ss][j]){   //该边是否在最短路上

                   addEdge(i,j,1);

                }

            }

         }

         printf("%d\n",maxFlow());

    }

    return 0;

}