# HDU3416 Marriage Match IV（最短路+最大流）

## Marriage Match IV

• Time Limit: 2000/1000 MS (Java/Others)
• Memory Limit: 32768/32768 K (Java/Others)
• Total Submission(s): 5663
• Accepted Submission(s): 1655

### 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.
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

starvae@HDU

### Source

HDOJ Monthly Contest – 2010.06.05

### 链接

http://acm.hdu.edu.cn/showproblem.php?pid=3416

### 题意

n个点m条边带权有向图，问每条边最多只能走一次时从A到B的最短路径数量。

### 题解

• dijkstra(S, dist1); // 跑S到所有点的最短路
• dijkstra(T, dist2); // 跑T到所有点的最短路
• dist1[a[i]] + c[i] + dist2[b[i]] == dist1[T] // 最短路上的边

### 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 200010;
int dist1[maxn], dist2[maxn];
bool vis[maxn];
int n, m, N;

struct Node
{
int v, c;
Node(int _v, int _c): v(_v), c(_c) {}
bool operator < (const Node & r) const
{
return c > r.c;
}
};

struct Edge
{
int to, cost;
Edge(int _to, int _cost): to(_to), cost(_cost) {}
};

vector <Edge> edge[maxn];

void addedge(int u, int v, int w) // 最短路加边
{
edge[u].push_back(Edge(v, w));
}

void dijkstra(int s, int dist[]) // 最短路
{
for (int i = 1; i <= N; ++i)
{
dist[i] = inf;
vis[i] = false;
}
dist[s] = 0;
priority_queue <Node> Q;
Q.push(Node(s, dist[s]));
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v;
if (vis[u])
continue;
vis[u] = true;
for (int i = 0; i < edge[u].size(); ++i)
{
int v = edge[u][i].to, cost = edge[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost)
{
dist[v] = dist[u] + cost;
Q.push(Node(v, dist[v]));
}
}
}
}

struct Edges
{
int u, v, cap;
Edges() {}
Edges(int u, int v, int cap): u(u), v(v), cap(cap) {}
} es[maxm];
int R, S, T;
vector <int> tab[maxn]; // 边集
int dis[maxn];
int current[maxn];

void addedges(int u, int v, int cap) // 最大流加边
{
tab[u].push_back(R);
es[R++] = Edges(u, v, cap); // 正向边
tab[v].push_back(R);
es[R++] = Edges(v, u, 0); // 反向边容量为0
// 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2
}

int BFS()
{
queue <int> q;
q.push(S);
memset(dis, 0x3f, sizeof(dis));
dis[S] = 0;
while (!q.empty())
{
int h = q.front();
q.pop();
for (int i = 0; i < tab[h].size(); i++)
{
Edges &e = es[tab[h][i]];
if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
{
dis[e.v] = dis[h] + 1;
q.push(e.v);
}
}
}
return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点
}

int dinic(int x, int maxflow)
{
if (x == T)
return maxflow;
// i = current[x] 当前弧优化
for (int i = current[x]; i < tab[x].size(); i++)
{
current[x] = i;
Edges &e = es[tab[x][i]];
if (dis[e.v] == dis[x] + 1 && e.cap > 0)
{
int flow = dinic(e.v, min(maxflow, e.cap));
if (flow)
{
e.cap -= flow; // 正向边流量降低
es[tab[x][i] ^ 1].cap += flow; // 反向边流量增加
return flow;
}
}
}
return 0; // 找不到增广路 退出
}

int DINIC()
{
int ans = 0;
while (BFS()) // 建立分层图
{
int flow;
memset(current, 0, sizeof(current)); // BFS后应当清空当前弧数组
while (flow = dinic(S, 0x3f3f3f3f)) // 一次BFS可以进行多次增广
ans += flow;
}
return ans;
}

int a[maxm], b[maxm], c[maxm];

int main()
{
int kase;
scanf("%d", &kase);
while (kase--)
{
scanf("%d%d", &n, &m);
N = n;
for (int i = 0; i <= N; ++i) // 清空
edge[i].clear();
for (int i = 1; i <= m; ++i) // 先正向加边
{
scanf("%d%d%d", &a[i], &b[i], &c[i]);
}
scanf("%d%d", &S, &T);
dijkstra(S, dist1); // 跑S到所有点的最短路
for (int i = 0; i <= N; ++i) // 清空
edge[i].clear();
for (int i = 1; i <= m; ++i) // 反向加边
dijkstra(T, dist2); // 跑T到所有点的最短路
R = 0;
for (int i = 0; i <= N; i++)
tab[i].clear();
for (int i = 1; i <= m; ++i)
{
if (a[i] != b[i] && dist1[a[i]] + c[i] + dist2[b[i]] == dist1[T]) // 最短路上的边
}