首页 > 代码库 > hdu3416 Marriage Match IV 最短路+ 最大流
hdu3416 Marriage Match IV 最短路+ 最大流
此题的大意：给定一幅有向图，求起点到终点（都是固定的）的不同的最短路有多少条。不同的最短路是说不能有相同的边，顶点可以重复。并且图含有平行边。
看了题以后，就想到暴力，但是暴力往往是不可取的。（暴力的最坏情况下的时间复杂度是O(n^3)）。我说的暴力是求一次最短路以后，把最短路上的边全部去掉（权值设为INF）。
最短路可以有很多条，但是最短路的值只有一个。根据这个，我们可以判断某条边是否在最短路上。
建图（单向边），求最短路，起点就是输入的起点。枚举每一条边，如果满足dist[i]+Map[i][j]==dist[j]，就建立一条权值为i,j之间长度等于最短边的边数。
我的做法是在建正向图的时候，用数组en[][]记录两点之间的长度等于最短边的边数。
看上去代码蛮长的，其实就2个模版，main()才是需要自己去写的。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N = 1010, M=2000010, INF=100001000; 7 int dist[N], Map[N][N], pre[N],en[N][N]; 8 bool p[N]; 9 void Dijkstra(int s,int n) 10 { 11 int i,j,k, MIN; 12 for(i=1; i<=n; i++) //初始化 13 { 14 p[i]=0; 15 if(i!=s) 16 { 17 dist[i]= Map[s][i]; 18 pre[i]=s; 19 } 20 } 21 dist[s]=0; 22 p[s]=1; 23 for(i=1; i<n; i++) //循环n-1次 24 { 25 MIN=INF; 26 k=0; 27 for(j=1; j<=n; j++) 28 { 29 if(!p[j]&&dist[j]<MIN) 30 { 31 MIN= dist[j]; 32 k=j; 33 } 34 } 35 if(!k) return ;//没有点可以扩展 36 p[k]=1; //将k从Vb中除去,加入Va 37 for(j=1; j<=n; j++) 38 { 39 if(!p[j]&&Map[k][j]!=INF&&dist[j]>dist[k]+Map[k][j]) 40 { 41 dist[j]= dist[k] + Map[k][j]; 42 pre[j]=k; 43 } 44 } 45 } 46 } 47 struct node 48 { 49 int to,next,w; 50 }edge[M]; 51 int head[N],numh[N],h[N],cure[N]; 52 int ans,tot; 53 void SAP(int s, int e,int n) 54 { 55 int flow,u,tmp,neck,i; 56 ans=0; 57 for(i=1;i<=n;i++) 58 cure[i]=head[i]; 59 numh[0]=n; 60 u=s; 61 while(h[s]<n) 62 { 63 if(u==e) 64 { 65 flow =INF; 66 for(i=s;i!=e;i=edge[cure[i]].to) 67 { 68 if(flow>edge[cure[i]].w) 69 { 70 neck=i; 71 flow =edge[cure[i]].w; 72 } 73 } 74 for(i=s;i!=e;i=edge[cure[i]].to) 75 { 76 tmp=cure[i]; 77 edge[tmp].w-=flow; 78 edge[tmp^1].w+=flow; 79 } 80 ans+=flow; 81 u=neck; 82 } 83 for(i=cure[u];i!=-1;i=edge[i].next) 84 if(edge[i].w && h[u]==h[edge[i].to]+1) break; 85 if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} 86 else 87 { 88 if(0==--numh[h[u]]) break; //GAP优化 89 cure[u]=head[u]; 90 for(tmp=n,i=head[u];i!=-1;i=edge[i].next) 91 if(edge[i].w) tmp=min(tmp, h[edge[i].to]); 92 h[u]=tmp+1; 93 ++numh[h[u]]; 94 if(u!=s) u=pre[u]; 95 } 96 } 97 } 98 void init() 99 {100 tot=0;101 memset(head,-1,sizeof(head));102 memset(pre,-1,sizeof(pre));103 memset(h,0,sizeof(h));104 memset(numh,0,sizeof(numh));105 106 }107 void addedge(int i,int j,int w)108 {109 edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;110 edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++;111 }112 int main()113 {114 //freopen("test.txt","r",stdin);115 int n,m,i,j,k,s,e,cas;116 scanf("%d",&cas);117 while(cas--)118 {119 scanf("%d%d",&n,&m);120 for(i=1;i<=n;i++)121 for(j=1;j<=n;j++)122 {123 Map[i][j]=INF;124 en[i][j]=0;125 }126 while(m--)127 {128 scanf("%d%d%d",&i,&j,&k);129 if(i==j) continue;130 if(Map[i][j]>k) {Map[i][j]=k, en[i][j]=1;}131 else if (Map[i][j]==k) {en[i][j]++;}132 }133 scanf("%d%d",&s,&e);134 Dijkstra(s,n);135 init();136 for(i=1;i<=n;i++)137 {138 for(j=1;j<=n;j++)139 {140 if(Map[i][j]!=INF)141 {142 if(dist[i]+Map[i][j]==dist[j])143 addedge(i,j,en[i][j]);144 }145 }146 }147 SAP(s,e,n);148 printf("%d\n",ans);149 }150 return 0;151 }
hdu3416 Marriage Match IV 最短路+ 最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。