Marriage Match IV
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
题意：给出点跟边，点之间存在重边，有个人想从起点到终点。
求：从起点在保证最短路值的条件下有多少条弱独立轨（即边只能经过一次，但点能通过多次）能到终点。
分析：题意从起点到终点，问多少条弱独立轨，显然就是最大流。
点之间允许重边，那权值小的边肯定能制造出更短的路径，于是对每两点间，只需要保存权值最小的边，但最小的边也有重边，所以可以每两个点间的最小边数。那这两个点就可以被经过的次数就是最小边数了。
接下来就是确定哪些边是在最短路上的边了。这个要求建两次图，题意中给出了起点s跟终点t。一次是按原图，计算所有点到s的最短路dis1；另一次是将图反过来，计算所有点到t的最短路dis2；接下来对某个边（a,b).如果dis1[a] + dis2[b] + w(a,b) == dis1[t];则表示这个条边在最短路上。将所有这些在最短路上的边建成一个图，容量是每两个点间的最少边数。最大流即为答案。
代码：
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <iostream>
#define Min(a, b) (a) < (b) ? a : b
#define Max(a, b) (a) > (b) ? a : b
using namespace std;
const int MAXN = 2005;
const int MAXM = 210000;
const int INF = 1100000000;
struct Edge
{
int st, ed;
int next;
int flow;
int cap;
}edge[MAXM];
int head[MAXN], level[MAXN], que[MAXN], E;
void add(int u, int v, int w)
{
edge[E].flow = 0;
edge[E].cap = w;
edge[E].st = u;
edge[E].ed = v;
edge[E].next = head[u];
head[u] = E++;
edge[E].flow = 0;
edge[E].cap = 0;
edge[E].st = v;
edge[E].ed = u;
edge[E].next = head[v];
head[v] = E++;
}
int dinic_bfs(int src, int dest, int ver)
{
int i, j;
for (i = 0; i <= ver; i++)
{
level[i] = -1;
}
int rear = 1;
que[0] = src; level[src] = 0;
for(i = 0; i < rear; i++)
{
for(j = head[que[i]]; j != -1; j = edge[j].next)
{
if(level[edge[j].ed] == -1 && edge[j].cap > edge[j].flow)
{
level[edge[j].ed] = level[que[i]]+1;
que[rear++] = edge[j].ed;
}
}
}
return level[dest] >= 0;
}
int dinic_dfs(int src, int dest, int ver)
{
int stk[MAXN], top = 0;
int ret = 0, cur, ptr, pre[MAXN], minf, i;
int del[MAXN];
for (i = 0; i <= ver; i++)
{
del[i] = 0;
}
stk[top++] = src;
pre[src] = src;
cur = src;
while(top)
{
while(cur != dest && top)
{
for(i = head[cur]; i != -1; i = edge[i].next)
{
if(level[edge[i].ed] == level[cur] + 1 && edge[i].cap > edge[i].flow && !del[edge[i].ed])
{
stk[top++] = edge[i].ed;
cur = edge[i].ed;
pre[edge[i].ed] = i;
break;
}
}
if(i == -1)
{
del[cur] = 1;
top--;
if(top) cur = stk[top-1];
}
}
if(cur == dest)
{
minf = INF;
while(cur != src)
{
cur = pre[cur];
if(edge[cur].cap - edge[cur].flow < minf) minf = edge[cur].cap - edge[cur].flow;
cur = edge[cur].st;
}
cur = dest;
while(cur != src)
{
cur = pre[cur];
edge[cur].flow += minf;
edge[cur^1].flow -= minf;
if(edge[cur].cap - edge[cur].flow == 0)
{
ptr = edge[cur].st;
}
cur = edge[cur].st;
}
while(top > 0&& stk[top-1] != ptr) top--;
if(top) cur = stk[top-1];
ret += minf;
}
}
return ret;
}
int Dinic(int src, int dest, int ver)
{
int ret = 0, t;
while(dinic_bfs(src, dest, ver))
{
t = dinic_dfs(src, dest, ver);
if(t) ret += t;
else break;
}
return ret;
}
//下面是求最短路用到的数据结构。
struct T
{
int v, w, next;
}fn[MAXM];
int th, g[MAXN], dis1[MAXN], dis2[MAXN], pre[MAXN], visit[MAXN];
int map[MAXN][MAXN], cat[MAXN][MAXN];
void insert(int u, int v, int w)
{
fn[th].v = v, fn[th].w = w, fn[th].next = g[u], g[u] = th++;
}
void spfa(int s, int t, int n, int * dis, int sign)
{
int i, j, u, v;
th = 0;
for (i = 0; i <= n; i++)
{
g[i] = -1;
}
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (map[i][j] < INF)
{
if (sign)
{
insert(i, j, map[i][j]);
}
else
{
insert(j, i, map[i][j]);
}
}
}
}
for (i = 0; i <= n; i++)
{
visit[i] = 0;
dis[i] = INF;
}
queue<int> que;
dis[s] = 0, visit[s] = 1;
que.push(s);
while (!que.empty())
{
u = que.front();
que.pop();
visit[u] = 0;
for (i = g[u]; i != -1; i = fn[i].next)
{
v = fn[i].v;
if (dis[v] > dis[u] + fn[i].w)
{
dis[v] = dis[u] + fn[i].w;
if (!visit[v])
{
que.push(v);
visit[v] = 1;
}
}
}
}
}
void build (int s, int t, int n)
{
int i, j, v;
E = 0;
for (i = 0; i <= n + 10; i++)
{
head[i] = -1;
}
for (i = 1; i <= n; i++)
{
for (j = g[i]; j != -1; j = fn[j].next)
{
v = fn[j].v;
if (dis1[i] + dis2[v] + fn[j].w == dis1[t])//对所有边满足最短路上的边建图。
{
add(i, v, cat[i][v]);
}
}
}
int ans = Dinic(s, t, n + 10);
printf("%d\n", ans);
}
int main()
{
int t, n, m, ver, i, j, u, v, w;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
map[i][j] = INF;
cat[i][j] = 0;
}
}
while (m--)
{
scanf("%d%d%d", &u, &v, &w);
if (u != v)
{
if (map[u][v] > w)
{
map[u][v] = w;
cat[u][v] = 1;
}
else if (map[u][v] == w)
{
cat[u][v]++;//边容量++
}
}
}
int s, t, flow;
scanf("%d%d", &s, &t);
spfa(t, s, n, dis2, 0);
spfa(s, t, n, dis1, 1);
build(s, t, n);
}
return 0;
}
/*
2 2
1 2 1
1 2 2
1 2
2 1
1 2 1
1 2
3 2
1 2 1
2 3 4
*/