2016-09-17

HDU 5889 Barricade【BFS + 最小割】

题目链接：

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

题意：

给定无向图，要求在所有最短路上设置一个路障，使得无论走那条最短路都会遇到路障，问最小花费。

分析：

很裸的最短路上的最小割。把最短路拿出来重新建图，注意新建的是有向图(wa了超级久)，然后跑一遍最小割即可。
在求最短路的时候，最初很傻逼的用$vector$保存每个结点的爸爸们QAQ，其实只要正着求一遍bfs，再倒着求一遍，找到满足$d2[u] + d1[v] + 1 = d1[n]$的点即可。
还有一种罗大神的方法，把所有在最短路上即满足$d[v] = d[u] + 1$的点都拿出来建图，因为求得是$1到n$的最大流，所以不在从$1到n$的最短路上也没有影响，这样只要$bfs$一次即可。

代码：

/*************************************************************************
    > File Name: 1011.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/17 12:40:35
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 2e4 + 5, maxm = 4e5 + 5, INF = 0x3f3f3f3f; 
struct edge{int to, cap, rev, flow;}e[maxm];
int d[maxm], iter[maxm];
int s, t;
struct EDGE{
    int to, next;
    int from;
    int val;
    bool flag;
}edges[maxm];
vector<edge>G[maxm * 2];
int head[maxn];
int tot;
void init()
{
    for(int i = 0; i < maxn; i++) G[i].clear();
    memset(head, -1, sizeof(head));
    tot = 0;
}
void Addedge(int from, int to, int cap)
{
    G[from].push_back((edge){to, cap, G[to].size(), 0});
    G[to].push_back((edge){from, 0, G[from].size()-1, 0});
}
void bfs()
{
    memset(d, -1, sizeof(d));
    queue<int>q;
    d[s] = 0;
    q.push(s);
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = 0; i < G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > e.flow && d[e.to] == -1){
                d[e.to] = d[v] + 1;
                q.push(e.to);
            }
        }
    }
}
int dfs(int v, int f)
{
    if(v == t) return f;
    for(int &i = iter[v]; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(e.cap > e.flow && d[v] == d[e.to] - 1){
            int tf = dfs(e.to, min(f, e.cap - e.flow));
            if(tf > 0){
                e.flow += tf;
                G[e.to][e.rev].flow -= tf;
                return tf;
            }
        }
    }
    return 0;
}
int max_flow()
{
    int flow = 0;
    for(;;){
        bfs();
        if(d[t]<0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while((f = dfs(s, INF))>0){
            flow += f;
        }
    }
}
void addedge(int u, int v, int val)
{
    edges[tot].flag = false;
    edges[tot].to = v;
    edges[tot].from = u;
    edges[tot].val = val;
    edges[tot].next = head[u];
    head[u] = tot++;
}
int d1[maxn], vis[maxn], d2[maxn];
void Bfs(int n)
{
    memset(d1, 0x3f, sizeof(d1));
    memset(vis, false, sizeof(vis));
    queue<int>q;
    q.push(1);
    d1[1] = 0;
    vis[1] = true;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; i != -1; i = edges[i].next){
            int v = edges[i].to;
            if(d1[v] < d1[u] + 1 || vis[v]) continue;
            d1[v] = d1[u] + 1;
            vis[v] = true;
            q.push(v);
        }
    }
    memset(vis, false, sizeof(vis));
    memset(d2, 0x3f, sizeof(d2));
    while(!q.empty()) q.pop();
    q.push(n);
    d2[n] = 0;
    vis[n] = true;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; i != -1; i = edges[i].next){
            int v = edges[i].to;
            if(d2[v] < d2[u] + 1 || vis[v]) continue;
            d2[v] = d2[u] + 1;
            vis[v] = true;
            q.push(v);
        }
    }
    for(int i = 0; i < tot; ++i){
        int u = edges[i].from, v = edges[i].to;
        if(d1[u] + d2[v] + 1 == d1[n] && d1[v] == d1[u] + 1){
            Addedge(u, v, edges[i].val);
        }
    }
}
int main (void)
{
    int T;scanf("%d", &T);
    while(T--){
        int n, m;scanf("%d%d", &n, &m);
        int u, v, x;
        init();
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &x);
            addedge(u, v, x);
            addedge(v, u, x);
        }
        Bfs(n);
        s = 1, t = n;
        printf("%d\n", max_flow());
    }
}