「zoj2760」How Many Shortest Path
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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
|
1 2 |
2 1 |
题解
floyd求出最短路，对于能在最短路上的边u->v流量为1
s-t的最大流即为答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<set> #define ll long long #define mod 1000000007 #define inf 1000000000 using namespace std; int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt,S,T; int last[105],h[105],q[105],cur[105]; int mp[105][105],dis[105][105]; struct edge{ int to,next,v; }e[100005]; void insert(int u,int v,int w) { // cout<<u<<' '<<v<<' '<<w<<endl; e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0; } bool bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); q[0]=S;h[S]=0; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=cur[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(f-used,e[i].v)); e[i].v-=w;e[i^1].v+=w; if(e[i].v)cur[x]=i; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } int dinic() { int tmp=0; while(bfs()) { for(int i=1;i<=n;i++)cur[i]=last[i]; tmp+=dfs(S,inf); } return tmp; } void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } void build() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mp[i][j]!=-1&&dis[S][i]+dis[j][T]+mp[i][j]==dis[S][T]) insert(i,j,1); } int main() { while(scanf("%d",&n)!=EOF) { cnt=1; memset(last,0,sizeof(last)); memset(dis,127/3,sizeof(dis)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { mp[i][j]=read(); if(mp[i][j]!=-1)dis[i][j]=mp[i][j]; } for(int i=1;i<=n;i++) dis[i][i]=0; S=read()+1;T=read()+1; if(S==T){puts("inf");continue;} floyd(); build(); printf("%d\n",dinic()); } return 0; } |
OI 课件=>
