Marriage Match IV
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6230 Accepted Submission(s): 1804
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3416
Description:
Do not sincere non-interference。
Like that show, now starvae also take part in a show, but it take place between city A and B. Starvae is in city A and girls are in city B. Every time starvae can get to city B and make a data with a girl he likes. But there are two problems with it, one is starvae must get to B within least time, it's said that he must take a shortest path. Other is no road can be taken more than once. While the city starvae passed away can been taken more than once.
So, under a good RP, starvae may have many chances to get to city B. But he don't know how many chances at most he can make a data with the girl he likes . Could you help starvae?
Input:
The first line is an integer T indicating the case number.(1<=T<=65)
For each case,there are two integer n and m in the first line ( 2<=n<=1000, 0<=m<=100000 ) ,n is the number of the city and m is the number of the roads.
Then follows m line ,each line have three integers a,b,c,(1<=a,b<=n,0<c<=1000)it means there is a road from a to b and it's distance is c, while there may have no road from b to a. There may have a road from a to a,but you can ignore it. If there are two roads from a to b, they are different.
At last is a line with two integer A and B(1<=A,B<=N,A!=B), means the number of city A and city B.
There may be some blank line between each case.
Output:
Output a line with a integer, means the chances starvae can get at most.
Sample Input:
3 7 8 1 2 1 1 3 1 2 4 1 3 4 1 4 5 1 4 6 1 5 7 1 6 7 1 1 7 6 7 1 2 1 2 3 1 1 3 3 3 4 1 3 5 1 4 6 1 5 6 1 1 6 2 2 1 2 1 1 2 2 1 2
Sample Output:
2 1 1
题意：
一个男生要去到一个城市找女生，他们两个的城市间有多条路径，现在他肯定想走最短路啦~
问他能走多少条最短路到女生的城市，并且要求这些最短路路径不能重复。
题解:
最近事情有点多，很久没更新博客了...
这题一开始我想的是费用流，但是T了。
正解是最大流，但是是经过“改造后”的最大流。这个最大流网络应该是由容量为1的，在原图最短路径上的边构成，最后我们跑个Dinic就行了。
要找最短路径上面的边，我们从起点spfa一次，再从终点spfa一次就行了。注意跑spfa建边的时候不要建双向边，我一开始就是这里WA了...
具体做法见代码：
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #include <vector> #define INF 1<<30 using namespace std; typedef long long ll; const int N =1005, M = 1e5+5; int n,m,s,t,T,mx; int d1[N],d2[N],d[N],vis[N],head[N]; pair <pair<int,int>,int> E[M]; struct Edge{ int v,next,c,w; }e[M<<1]; int tot; void adde(int u,int v,int c,int w){ e[tot].v=v;e[tot].c=c;e[tot].next=head[u];e[tot].w=w;head[u]=tot++; } void spfa(int S){ queue <int> q;q.push(S); memset(vis,0,sizeof(vis));vis[S]=1; for(int i=1;i<=n;i++) d2[i]=INF;d2[S]=0; while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(d2[v]>d2[u]+e[i].w){ d2[v]=d2[u]+e[i].w; if(!vis[v]){ vis[v]=1; q.push(v); } } } } } int bfs(){ memset(d,0,sizeof(d));d[s]=1; queue <int > q;q.push(s); while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(e[i].c>0 && !d[v]){ d[v]=d[u]+1; q.push(v); } } } return d[t]!=0; } int dfs(int u,int a){ if(u==t || a==0) return a; int flow=0,f; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(d[v]!=d[u]+1) continue ; f=dfs(v,min(a,e[i].c)); if(f>0){ e[i].c-=f; e[i^1].c+=f; flow+=f; a-=f; if(a==0) break; } } if(!flow) d[u]=-1; return flow; } int Dinic(){ int flow=0; while(bfs()) flow+=dfs(s,INF); return flow; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); tot=0;memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); E[i]=make_pair(make_pair(u,v),w); adde(u,v,1,w); } scanf("%d%d",&s,&t); spfa(s); for(int i=1;i<=n;i++) d1[i]=d2[i]; tot=0;memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ int u=E[i].first.first,v=E[i].first.second,w=E[i].second; adde(v,u,1,w); } spfa(t); mx=d1[t]; tot=0;memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ int u =E[i].first.first,v=E[i].first.second,w=E[i].second; if(d1[u]+d2[v]+w==mx){ adde(u,v,1,INF); adde(v,u,0,INF); } } printf("%d ",Dinic()); } return 0; }