zoj 2760 How Many Shortest Path//MAXFLOW

How Many Shortest Path
Time Limit: 10 Seconds     
Memory Limit: 32768 KB
Given a weighted directed graph, we define the shortest path as the path who has the smallest length among all the path connecting the source vertex to the target vertex. And if two path is said to be non-overlapping, it means that the two path has no common edge. So, given a weighted directed graph, a source vertex and a target vertex, we are interested in how many non-overlapping shortest path could we find out at most.
Input
Input consists of multiple test cases. The first line of each test case, there is an integer number N (1<=N<=100), which is the number of the vertices. Then follows an N * N matrix, represents the directed graph. Each element of the matrix is either non-negative integer, denotes the length of the edge, or -1, which means there is no edge. At the last, the test case ends with two integer numbers S and T (0<=S, T<=N-1), that is, the starting and ending points. Process to the end of the file.
Output
For each test case, output one line, the number of the the non-overlapping shortest path that we can find at most, or "inf"(without quote), if the starting point meets with the ending.
Sample Input
 

4
0 1 1 -1
-1 0 1 1
-1 -1 0 1
-1 -1 -1 0
0 3
5
0 1 1 -1 -1
-1 0 1 1 -1
-1 -1 0 1 -1
-1 -1 -1 0 1
-1 -1 -1 -1 0
0 4

 
Sample Output
 

2
1

  Author:
SHEN, Guanghao
Source:
ZOJ Monthly, September 2006
 
이 문제는 많은 것을 배웠다.
이전에 S-->T 중의 길 중 가장 긴 변의 가장 작은 경로의 수를 구하는 문제를 한 적이 있는데, 당시의 해법은 2분+네트워크 흐름이었다
이 문제는 최단로의 수량을 구하는 것인데, 뜻밖에도 인터넷 흐름으로 할 수 있다
우선 이전에 생각하지 못했던 것은 FLOYED로 I->J 이 변이 최단로에 있는지 계산할 수 있고, 이어서 만약에 있다면 1로 표시할 수 있다
주의, FLOYED의 과정은 틀리기 쉬우므로 원래의 그림의 변수를 바꾸지 마세요. 왜냐하면 원래의 I->J는 끝이 없을 수 있지만, 당신이 FLOYED를 한 후에 I->J가 끝이 있을 수 있습니다. 당신은 I->J를 이 옆에 넣을 수 있습니다. 그러면 틀렸습니다.
이어서 최대 흐름으로 할 수 있어요.
 
#include
#include
#include
using namespace std;
const int inf=100000000;
 
int n,s,t;
int flow[110][110],mat[110][110],gap[110],dist[110];
int map[110][110];
 
int find_path(int p,int limit=1<<30-1)
{
    if(p==n-1) return limit;
    for(int i=0;i    {
        if(dist[p]==dist[i]+1&&map[p][i]>0)
        {
            int t=find_path(i,min(limit,map[p][i]));
            if(t<0) return t;
            if(t>0)
            {
                map[p][i]-=t;
                map[i][p]+=t;
                return t;
            }
        }
    }
    int label=n;
    for(int i=0;i0)  label=min(label,dist[i]+1);
    if(--gap[dist[p]]==0||dist[0]>=n)  return -1;
    ++gap[dist[p]=label];
    return 0;
}
 
int iSAP()
{
    gap[0]=n;
    int maxflow=0,t=0;
    while((t=find_path(0))>=0)  maxflow+=t;
    return maxflow;
}
 
void buildgraph()
{
    memcpy(mat,flow,sizeof(flow));
    for(int k=1;k<=n;k++)
      for(int i=1;i<=n;i++)
      {
           if(mat[i][k]==inf)  continue;
           for(int j=1;j<=n;j++)
           {
               if(mat[k][j]==inf) continue;
               mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
           }
      }
    memset(map,0,sizeof(map));
    for(int i=1;i<=n;i++)
    {
      if(mat[s][i]==inf) continue;
      for(int j=1;j<=n;j++)
      {
          if(mat[j][t]==inf) continue;
          map[i][j]=(flow[i][j]!=inf && mat[s][i]+flow[i][j]+mat[j][t]==mat[s][t]);
      }
    }
}
 
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(flow,0,sizeof(flow));
        memset(gap,0,sizeof(gap));
        memset(dist,0,sizeof(dist));
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
          {
              scanf("%d",&flow[i][j]);
              if(i==j) flow[i][j]=0;
              else if(flow[i][j]==-1) flow[i][j]=inf;
          }
        scanf("%d%d",&s,&t);
        s++;t++;
        if(s==t) printf("inf/n");
        else
        {
            buildgraph();
            map[0][s]=inf;
            map[t][n+1]=inf;
            n=n+2;
            printf("%d/n",iSAP());
        }
    }
    return 0;
}