How Many Shortest Path

zoj2760:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2760

題意：給你一張有向帶權圖，然后問你最短路徑有多少條。

題解：這一題用到了網絡流，一開始，我想到用找到一條最短路，然后刪除這條，然后繼續找，發現這樣是不對。然后，看了別人的題解，發現，用網絡流搞。就是把所有的最短路徑的邊對應的點之間建邊，邊的容量是1，然后跑網絡流。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<queue>
  6 #define INF 100000000
  7 using namespace std;
  8 const int N=205;
  9 const int M=30000;
 10 int mp[N][N],dist[N][N];
 11 struct Node{
 12    int v;
 13    int f;
 14    int next;
 15 }edge[M];
 16 int n,m,u,v,s,t,cnt,sx,ex;
 17 int head[N],pre[N];
 18 void init(){
 19     cnt=0;
 20     memset(head,-1,sizeof(head));
 21 }
 22 void add(int u,int v,int w){
 23     edge[cnt].v=v;
 24     edge[cnt].f=w;
 25     edge[cnt].next=head[u];
 26     head[u]=cnt++;
 27     edge[cnt].f=0;
 28     edge[cnt].v=u;
 29     edge[cnt].next=head[v];
 30     head[v]=cnt++;
 31 }
 32 bool BFS(){
 33   memset(pre,0,sizeof(pre));
 34   pre[sx]=1;
 35   queue<int>Q;
 36   Q.push(sx);
 37  while(!Q.empty()){
 38      int d=Q.front();
 39      Q.pop();
 40      for(int i=head[d];i!=-1;i=edge[i].next    ){
 41         if(edge[i].f&&!pre[edge[i].v]){
 42             pre[edge[i].v]=pre[d]+1;
 43             Q.push(edge[i].v);
 44         }
 45      }
 46   }
 47  return pre[ex]>0;
 48 }
 49 int dinic(int flow,int ps){
 50     int f=flow;
 51      if(ps==ex)return f;
 52      for(int i=head[ps];i!=-1;i=edge[i].next){
 53         if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){
 54             int a=edge[i].f;
 55             int t=dinic(min(a,flow),edge[i].v);
 56               edge[i].f-=t;
 57               edge[i^1].f+=t;
 58             flow-=t;
 59              if(flow<=0)break;
 60         }
 61 
 62      }
 63       if(f-flow<=0)pre[ps]=-1;
 64       return f-flow;
 65 }
 66 int solve(){
 67     int sum=0;
 68     while(BFS())
 69         sum+=dinic(INF,sx);
 70     return sum;
 71 }
 72 int temp;
 73 int main() {
 74     while(~scanf("%d",&n)){
 75          init();
 76          for(int i=1;i<=n;i++){
 77             for(int j=1;j<=n;j++){
 78                   scanf("%d",&temp);
 79                   if(i==j)mp[i][j]=0;
 80                   else if(temp==-1)mp[i][j]=INF;
 81                   else
 82                     mp[i][j]=temp;
 83                     dist[i][j]=mp[i][j];
 84             }
 85          }
 86           scanf("%d%d",&s,&t);
 87           if(s!=t){
 88             s++;t++;
 89             for(int k=1;k<=n;k++)
 90                for(int i=1;i<=n;i++)
 91                 for(int j=1;j<=n;j++){
 92                  dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
 93             }
 94             for(int i=1;i<=n;i++){
 95                 for(int j=1;j<=n;j++){
 96                    if(mp[i][j]<INF&&dist[s][i]+mp[i][j]+dist[j][t]==dist[s][t])
 97                      add(i,j,1);
 98                 }
 99             }
100             sx=s;ex=t;
101             printf("%d\n",solve());
102         }
103          else
104             printf("inf\n");
105         }
106     return 0;
107 }

View Code

轉載于:https://www.cnblogs.com/chujian123/p/3948549.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/375652.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/375652.shtml
英文地址，請注明出處：http://en.pswp.cn/news/375652.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！