HDU-5889-Barricade【2016青岛网络】【spfa】【最小割】

发布时间：2020-12-13 21:18:40 所属栏目：PHP教程来源：网络整理

导读：5889-Barricade Problem Description The empire is under attack again. The general of empire is planning to defend his castle. The land can be seen as N towns and M roads,and each road has the same length and connects two towns. The town num

5889-Barricade

Problem Description
The empire is under attack again. The general of empire is planning to defend his castle. The land can be seen as N towns and M roads,and each road has the same length and connects two towns. The town numbered 1 is where general’s castle is located,and the town numbered N is where the enemies are staying. The general supposes that the enemies would choose a shortest path. He knows his army is not ready to fight and he needs more time. Consequently he decides to put some barricades on some roads to slow down his enemies. Now,he asks you to find a way to set these barricades to make sure the enemies would meet at least one of them. Moreover,the barricade on the i-th road requires wi units of wood. Because of lacking resources,you need to use as less wood as possible.

Input
The first line of input contains an integer t,then t test cases follow.
For each test case,in the first line there are two integers N(N≤1000) and M(M≤10000).
The i-the line of the next M lines describes the i-th edge with three integers u,v and w where 0≤w≤1000 denoting an edge between u and v of barricade cost w.

Output
For each test cases,output the minimum wood cost.

Sample Input
1
4 4
1 2 1
2 4 2
3 1 3
4 3 4

Sample Output
4

题目链接：HDU⑸889

题目大意：给出n个点，m条路径，每条路径长度为1，敌人从m点攻击1点，敌人总是选择最短路径来进攻我方，为了禁止敌人，我们要把1些路封死，每条路径封死需要1些花费，求最小花费。

题目思路：首先用spfa处理出最短路中的边，然后做1遍最大流求出最小割。

可参考HDU⑶416

以下是代码:

#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <list>
using namespace std;
#define LL long long
#define MAXN 1005
struct node
{
    int v,len,w;  //终点、长度
    node(int a,int b,int c){
        v = a,len = b,w = c;
    }
};
struct edge
{
    int to,cap,rev;
    edge(int a,int c){
        to = a,cap = b,rev = c;
    }
};
int n;
vector <node> g[MAXN];
vector <edge> G[MAXN];
int d[MAXN];
bool used[MAXN];//DFS中用到的访问标记
void addEdge(int u,int v,int cap)
{
    G[u].push_back(edge(v,G[v].size()));
    G[v].push_back(edge(u,0,G[u].size()-1));
}
//通过DFS寻到增广路
int dfs(int v,int t,int f){
    if(v == t)
        return f;
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(!used[e.to] && e.cap > 0){
            int d = dfs(e.to,t,min(f,e.cap));
            if(d > 0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

//求解从s到t的最大流
int max_flow(int s,int t){
    int flow = 0;
    while(1){
        memset(used,false,sizeof(used));
        int f = dfs(s,99999999);
        if(f == 0)
            return flow;
        flow += f;
    }
}

void solve()
{
    for (int i = 1; i <= n; i++)
    {
        int len = g[i].size();
        for (int j = 0; j < len; j++)
        {
            int v = g[i][j].v;
            int l = g[i][j].len;
            int w = g[i][j].w;
            if (d[v] - d[i] == l)  //判断是不是为最短路
            {
                addEdge(i,v,w);
            }
        }
    }
}

void SPFA(int x)  //x为出发点
{
    int v[MAXN];
    memset(v,sizeof(v));
    queue<int>q;
    q.push(x);
    v[x] = 1;d[x] = 0;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        v[nod] = 0;
        for(int i = 0;i < g[nod].size();i++)
        {
            int nxtnod = g[nod][i].v;
            if(d[nxtnod] > d[nod] + g[nod][i].len)
            {
                d[nxtnod] = d[nod] + g[nod][i].len;
                if(!v[nxtnod])
                {
                    v[nxtnod] = 1;
                    q.push(nxtnod);
                }
            }
        }
    }
}
void init()
{
    memset(d,1,sizeof(d));
    for (int i = 0; i < MAXN-1; i++)
    {
        g[i].clear();
        G[i].clear();
    }
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int m;
        cin >> n >> m;
        init();

        for (int i = 0; i < m; i++)
        {
            int u,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u].push_back(node(v,w));
            g[v].push_back(node(u,w));
        }
        SPFA(1);
        solve();
        long long ans = max_flow(1,n);
        printf("%lldn",ans);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!