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

Sample Output

2
1
1

Author

starvae@HDU

Source

HDOJ Monthly Contest – 2010.06.05

链接

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

题意

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

题解

因为限制了每条边最多只能走一次，所以不能直接用最短路来搞。但是我们可以转化为网络流，每条边只能走一次，所以可以设置边的容量为1。当然，首先需要找到在最短路上的边，可以通过两遍最短路求得，然后用这些边跑最大流得到的就是答案。

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]);
            addedge(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) // 反向加边
            addedge(b[i], a[i], c[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]) // 最短路上的边
                addedges(a[i], b[i], 1);
        }
        int ans = DINIC(); // 求最大流
        printf("%d\n", ans);
    }
    return 0;
}

The end.
2018-09-08 星期六