题意:求出1到N 的无向图的无重复边的最短路径数(即所有的最短路径没有公共边)
分析:先求出最短路,再找出所有属于最短路的边(满足dist[u]+g[u][v]==dist[v]),把有向边(u,v)加入到新图中,容量为1,(即每条边只能用一次),最后求一次源点为1,汇点为t的最大流即可
View Code
#include<iostream> #include<algorithm> #include<string> #include<vector> #include<stack> using namespace std; const int N = 1500+10; int n,dist[N],g[N][N],Q[N]; bool vis[N]; int size,head[N],dis[N],gap[N],pre[N],cur[N]; struct edge { int v,w,next; edge(){} edge(int v,int next,int w=0):v(v),next(next),w(w){} }E[N*N]; inline void init() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=INT_MAX; } inline void insert(int u,int v,int w) { E[size]=edge(v,head[u],w); head[u]=size++; E[size]=edge(u,head[v],0); head[v]=size++; } int ISAP(int src,int des) { int maxflow=0; memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); for(int i=0;i<=n;i++) cur[i]=head[i]; int u =pre[src]=src; int aug=-1; while(dis[src]<n) { loop: for(int &i=cur[u];i!=-1;i=E[i].next) { int v=E[i].v; if(E[i].w && dis[u]==dis[v]+1) { aug=min(aug,E[i].w); pre[v]=u; u=v; if(v==des) { maxflow+=aug; for(u=pre[u];v!=src;v=u,u=pre[u]) { E[cur[u]].w-=aug; E[cur[u]^1].w+=aug; } aug=INT_MAX; } goto loop; } } int mdis=n; for(int i=head[u];i!=-1;i=E[i].next) { int v=E[i].v; if(E[i].w && mdis>dis[v]) { cur[u]=i; mdis=dis[v]; } } if((--gap[dis[u]])==0) break; gap[dis[u]=mdis+1]++; u=pre[u]; } return maxflow; } void SPFA(int s) { int i,pri,end,p; memset(vis,false,sizeof(vis)); for(int i=0;i<N;i++) Q[i]=0; for(int i=1;i<=n;i++) dist[i]=INT_MAX; dist[s]=0; vis[s]=true; Q[1]=s;pri=1;end=2; while(pri<end) { p=Q[pri]; for(int i=1;i<=n;i++) { if(g[p][i] != INT_MAX && dist[p]+g[p][i]<dist[i]) { dist[i]=dist[p]+g[p][i]; if(!vis[i]) { Q[end++]=i; vis[i]=1; } } } vis[p]=0; pri++; } return ; } void build() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) if(g[i][j]!=INT_MAX && dist[i]+g[i][j]==dist[j]) insert(i,j,1); } } int main() { int T,a,b,c; scanf("%d",&T); while(T--) { scanf("%d",&n); init(); while(true) { scanf("%d %d %d",&a,&b,&c); if(!(a||b||c)) break; if(g[a][b]>c) g[a][b]=g[b][a]=c; } size=0; memset(head,-1,sizeof(head)); SPFA(1); if(dist[n]==INT_MAX)//不存在最短路 { puts("0"); continue; } build();//建图 printf("%d\n",ISAP(1,n)); } return 0; }