zoj How Many Shortest Path

zoj How Many Shortest Path

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 
#include 
#include 
#include 
#include 
#include 
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 edges;
vector 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 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;
}