链接：http://acm.hdu.edu.cn/showproblem.php?pid=3416
题意：starvae在城市A，要去城市B约妹子，要走最短路，并且每段路只能走一次，不能重复走。
题解：在走最短路的情况下，有多少条路从A到B，并且每条路是不重复的（路上经过的任何一条边都不可以重复）。首先是求最短路，然后根据所求的最短路找到这写最短路上的边，将这些边建图，求一次最大流。因为边只能走一次，所以每条边的容量是1，不用拆点（因为城市可以多次经过)。
代码：
#include <stdio.h> #include <algorithm> #include <math.h> #include <string.h> #include <vector> #include <queue> #include <map> #include <stack> #include <iostream> #define pi acos(-1.0) #define INF 0x3f3f3f3f using namespace std; #define ll long long const int maxn=10100; int head[maxn],cnt=0; struct edge { int t,f,next; }e[500010]; void init() { memset(head,-1,sizeof head); cnt=0; } void add_edge(int u,int v,int f) { e[cnt].t=v;e[cnt].f=f; e[cnt].next=head[u];head[u]=cnt++; e[cnt].t=u;e[cnt].f=0; e[cnt].next=head[v];head[v]=cnt++; } vector<pair<int,int> > mp[maxn]; bool vis[maxn];int dis[maxn]; void spfa(int s,int e) { memset(vis,0,sizeof vis); memset(dis,INF,sizeof dis); queue<int>q; q.push(s),dis[s]=0,vis[s]=false; while(!q.empty()) { int k=q.front();q.pop(); vis[k]=0; for(int i=0;i<mp[k].size();i++) { int v=mp[k][i].first,w=mp[k][i].second; if(dis[v]>dis[k]+w) { dis[v]=dis[k]+w; if(!vis[v]) vis[v]=1,q.push(v); } } } } void getedge(int n) { for(int i=1;i<=n;i++) for(int j=0;j<mp[i].size();j++) { int v=mp[i][j].first,w=mp[i][j].second; if(dis[v]==dis[i]+w) add_edge(i,v,1);//,printf("build %d %d %d ",i,v,1); } } bool bfs(int s,int t) { memset(dis,-1,sizeof dis); queue<int > q; dis[s]=1;q.push(s); while(!q.empty()) { int k=q.front();q.pop(); for(int i=head[k];i!=-1;i=e[i].next) { int v=e[i].t; if(e[i].f>0&&dis[v]==-1) { dis[v]=dis[k]+1; if(v==t) return 1; q.push(v); } } } return dis[t]!=-1; } int cur[maxn]; int dfs(int top,int t,int flow) { if(top==t) return flow; int ans=0,x=0; for(int i=cur[top];~i;i=e[i].next) { int to=e[i].t; if(e[i].f>0&&dis[to]==dis[top]+1) { x=dfs(to,t,min(flow-ans,e[i].f)); e[i].f-=x; e[i^1].f+=x; if(e[i].f) cur[top] = i; ans+=x; if(ans==flow) return flow; } } if(ans==0) dis[top]=0; return ans; } int main() { //freopen("C:\Users\Administrator\Desktop\a.txt","r",stdin); //ios::sync_with_stdio(false); //freopen("C:\Users\Administrator\Desktop\b.txt","w",stdout); int T,n,m; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) mp[i].clear(); init(); for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); mp[a].push_back(make_pair(b,c)); } int s,t; scanf("%d%d",&s,&t); spfa(s,t); getedge(n); //printf(" "); int ans=0; while(bfs(s,t)) { for(int i=0;i<=3*n;i++) cur[i]=head[i]; ans+=dfs(s,t,INF); } printf("%d ",ans); } return 0; }