Marriage Match IV
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3147 Accepted Submission(s): 946
Problem 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.
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.
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
题意：
有n个城市，m条边，a到b耗费为c，为单向边。要求从s到t的最短路径有多少条，每一条边只能走一次。
思路:
如果每天边不一定走一次的话，那么可以通过树形dp来求解。但是这里每条边只能走一次，也就是说每条路径上面的边的流量为1，从起点到终点求一次最大流即可。这样题目就能够用最大流来解决。对于建立新的图，可以先从终点到起点求一次最短路，然后从起点开始dfs，并且维护now[]数组，表示从起点到这个点的路径长度，
如果now[rt] + dis[t] + edge[i].val == dis[S]（dis[]的起点是原本图中的终点），那么说明这两个点是最短路上的点，那么可以连边，流量为1,。跑一次最大流解决问题了。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<time.h>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1000000001
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
struct node
{
int to;
int val;
int next;
}edge[MAXN**],e[MAXN**];
int ind,pre[MAXN],vis[MAXN],dis[MAXN],pre1[MAXN],ind1;
int now[MAXN],S,T;
int n,m;
void add1(int x,int y,int z)
{
e[ind1].to = y;
e[ind1].val = z;
e[ind1].next = pre1[x];
pre1[x] = ind1 ++;
}
void spfa()
{
for(int i = ; i <= n; i++){
dis[i] = INF;
vis[i] = ;
}
vis[T] = ;
dis[T] = ;
queue<int>q;
q.push(T);
while(!q.empty()){
int tp = q.front();
q.pop();
vis[tp] = ;
for(int i = pre1[tp]; i != -; i = e[i].next){
int t = e[i].to;
if(dis[t] > dis[tp] + e[i].val){
dis[t] = dis[tp] + e[i].val;
if(!vis[t]){
vis[t] = ;
q.push(t);
}
}
}
}
}
void add(int x,int y,int z)
{
edge[ind].to = y;
edge[ind].val = z;
edge[ind].next = pre[x];
pre[x] = ind ++;
}
void dfs1(int rt)
{
vis[rt] = ;
if(rt == T)return ;
for(int i = pre1[rt]; i != -; i = e[i].next){
int t = e[i].to;
if(now[rt] + dis[t] + e[i].val == dis[S]){
now[t] = now[rt] + e[i].val;
add(rt,t,);
add(t,rt,);
if(!vis[t]){
dfs1(t);
}
}
}
}
int bfs()
{
memset(vis,-,sizeof(vis));
queue<int>q;
vis[S] = ;
q.push(S);
while(!q.empty()){
int tp = q.front();
q.pop();
for(int i = pre[tp]; i != -; i = edge[i].next){
int t = edge[i].to;
if(vis[t] == - && edge[i].val){
vis[t] = vis[tp] + ;
q.push(t);
}
}
}
if(vis[T] == -)return ;
return ;
}
int dfs(int rt,int low)
{
int used = ;
if(rt == T)return low;
for(int i = pre[rt]; i != - && used < low; i = edge[i].next){
int t = edge[i].to;
if(vis[t] == vis[rt] + && edge[i].val){
int a = dfs(t,min(low-used,edge[i].val));
used += a;
edge[i].val -= a;
edge[i^].val += a;
}
}
if(used == )vis[rt] = -;
return used;
}
int x[MAXN*],y[MAXN*],z[MAXN*];
void Init(int flag)
{
ind1 = ;
memset(pre1,-,sizeof(pre1));
for(int i = ; i <= m; i++){
if(!flag){
add1(y[i],x[i],z[i]);
}
else {
add1(x[i],y[i],z[i]);
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i = ; i <= m; i++){
scanf("%d%d%d",&x[i],&y[i],&z[i]);
}
Init();
scanf("%d%d",&S,&T);
spfa();
Init();
ind = ;
memset(now,,sizeof(now));
memset(pre,-,sizeof(pre));
dfs1(S);
int ans = ;
while(bfs()){
while(){
int a = dfs(S,INF);
if(!a)break;
ans += a;
}
}
printf("%d\n",ans);
}
return ;
}