//题目大意：求两点之间最短路的条数，但是前提是已走过的路径不能重复//题目类型：最大流+最短路径//解题思路：首先用Dijkstra求出两点之间的最短路，然后判断每条边是否在最短路上，如果在最短路上，则流量自增1 ,然后求出最大流 #include <iostream>#include <algorithm>#include <queue>#include <cstdio>//#include <conio.h>using namespace std; const int narray = 1010; const int marray = 100010;const int INF=0x7fffffff; struct edge_T { int u; //起点(为了最大流建图方便) int v; //终点 int w; edge_T *next;}*adj[narray], edges[marray],*readj[narray],reedges[marray]; bool final[marray];struct node_T { int v; int len; bool operator < (const node_T &nod) const { return len > nod.len; }};int edgenum,reedgenum; //记录边的总数 int vn,en; //记录定点数和边数 int src,des;int dista[narray],distb[narray];
void addEdge(int u, int v, int w) { edge_T *ptr = &edges[edgenum]; ptr->u = u; ptr->v = v; ptr->w = w; ptr->next = adj[u]; //往前插入边 adj[u] = ptr; edgenum++;}void addReedge(int u,int v,int w){ edge_T *ptr = &reedges[reedgenum]; ptr->u = u; ptr->v = v; ptr->w = w; ptr->next = readj[u]; //往前插入边 readj[u] = ptr; reedgenum++;}int dijkstra(int s,int t,int dist[],int flag) { int i; priority_queue <node_T> Q; //使用优先级队列实现 node_T cur; edge_T *ptr; cur.v = s; cur.len = 0; Q.push(cur); for(int i = 1; i <= vn; i ++) { dist[i] = INF; } dist[s] = 0; while(!Q.empty()) { int v = Q.top().v; //优先级队列使用top() int len = Q.top().len; Q.pop(); if(dist[v]!=len) continue; if(flag == 1) ptr = adj[v]; else ptr = readj[v]; for(; ptr; ptr = ptr -> next) { int u = ptr -> v; int w = ptr -> w; if(dist[v] + w < dist[u]) { dist[u] = dist[v] + w; cur.v = u; cur.len = dist[u]; Q.push(cur); } } } return dist[t]; }
int capacity[narray][narray]; int pre[narray]; int num[narray]; int d[narray];
void init(int src,int des) { int i,j; queue<int> myqueue; myqueue.push(des); memset(num,0,sizeof(num)); for(i=1;i<=vn;++i) d[i] = INF; d[des] = 0; num[0] = 1; int frontint; while(!myqueue.empty()) { frontint = myqueue.front();myqueue.pop(); for(i=1;i<=vn;++i) { if(d[i]>=vn && capacity[i][frontint]>0) { d[i] = d[frontint]+1; myqueue.push(i); num[d[i]]++; } } }}int findarc(int t) { int i,j; for(i=1;i<=vn;++i) { if(capacity[t][i]>0 && d[t]==d[i]+1) return i; } return -1;}int relabel(int t) { int i,j; int mm = INF; for(i=1;i<=vn;++i) { if(capacity[t][i]>0) mm = min(mm,d[i]+1); } return mm==INF?vn:mm;}int maxFlow(int src,int des){ int sumflow = 0; int delta; int i=src; int j; memset(pre,-1,sizeof(pre)); while(d[src]<vn) { j = findarc(i); if(j>=0) { pre[j] = i; i = j; if(i==des) { delta = INF; for (i=des;i!=src;i=pre[i]) delta=min(delta,capacity[pre[i]][i]); for (i=des;i!=src;i=pre[i]) capacity[pre[i]][i] -= delta, capacity[i][pre[i]] += delta; sumflow += delta; } } else { int x = relabel(i); num[x]++; num[d[i]]--; if(num[d[i]]==0) return sumflow; d[i] = x; if(i!=src) i =pre[i]; } } return sumflow;}//见图并求最大流 void buildAndMaxFlow(int res){ int i,j; memset(capacity,0,sizeof(capacity)); for(i=1;i<edgenum;++i) //遍历所有的边(此处使用edgenum,因为可能存在负权回路的情况) { int u = edges[i].u; int v = edges[i].v; int w = edges[i].w; if(dista[u]+distb[v]+w==res) //如果边的起点到源点的距离+边的权值+边的终点到汇点的距离等于汇点到源点的距离 { capacity[u][v]++; } } init(src,des); //在求最大流之前首先初始化标顶 printf("%d\n",maxFlow(src,des));}int main() { //freopen("1.txt","r",stdin); int t; int i; int res; scanf("%d",&t); while(t--) { scanf("%d %d", &vn, &en); for(i = 1; i <= vn; i ++) { adj[i] = NULL; //初始化邻接表的指针 readj[i] = NULL; } edgenum = 1; //初始化边数 reedgenum =1; int u, v; int w; for(i = 1; i <= en; i ++) { scanf("%d%d%d", &u, &v, &w); if(u==v) continue; //判断是否有环 addEdge(u, v, w); addReedge(v,u,w); } scanf("%d%d",&src,&des); //分别求出途中各点到源点和终点之间的距离 dijkstra(src,des,dista,1); res = dijkstra(des,src,distb,2); buildAndMaxFlow(res); } //getch(); return 0;}
转载于:https://www.cnblogs.com/north_dragon/archive/2010/06/07/1753491.html
