MYF

HDU 5889 Barricade

Posted on | In | | Visitors

题目链接

HDU 5889

题目类型：最短路 ＋ 最小割（网络流）

题目分析

题目大意

n个点，m条边，然后给出每条无向边的u, v, w，表示一条边从u指向v但是如果要在这条边上设置障碍，需要耗费木材量w，注意，每条路的距离是相等的。现在将军在1点，而敌人在n点，敌人一定会从最短路来找将军，将军想要知道最少需要花费多少木材才能一定让敌人遇到障碍。

解析

一开始忽略了最短路的条件，直接跑了网络流，大意了。

题目中说敌人一定会从最短路来找将军，那么我们跑最小割的时候实际上只需要跑若干条最短路所形成的图即可。那么问题很容易的转化成了：如何找到所有最短路，以及如何在网络流的图中建图。找到最短路我们可以用SPFA，然后用一个vector记录到每个点最短距离的所有前驱。然后我们从终点，也就是n反向进行bfs就可以将网络流的图建出来了。此处要注意的是，在网络流中是单向加边，所以我们只考虑从将军到敌人的方向的边即可，这个其实也不难实现，因为我们BFS是从n点反向往1点跑的。

其他细节处理：输入的w用pair到int的映射存储，在这里我觉得这个用的还是挺合适的。

其实可以用ISAP写，但是怕网络赛的时候模版重了，所以使用dinic写了，不过跑的也挺快的，不知道是不是数据比较弱。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int Vmax = 1000+10;  //最大顶点数
const int Emax = 10000+10; //最大边数
map<PII, int>mp;
struct Dinic{
    int src,target,ecnt;//源点，汇点，边数
    int head[Vmax];//邻接表表头
    int cur[Vmax];
    int dis[Vmax];//从源点到该点的距离
    struct edge{
        int to,next,cap;
    }e[2*Emax];//边可能是双向的，故乘2
    
    void init(int start,int end){
        ecnt=0;
        src=start;
        target=end;
        memset(head,-1,sizeof(head));
    }
    
    void adde(int from,int to,int cap){
        e[ecnt].to=to;
        e[ecnt].cap=cap;
        e[ecnt].next=head[from];
        head[from]=ecnt++;
        
        e[ecnt].to=from;
        e[ecnt].cap=0;
        e[ecnt].next=head[to];
        head[to]=ecnt++;
    }
    
    bool BFS(){
        memset(dis, -1, sizeof(dis));
        dis[src]=0;
        queue<int>q;
        q.push(src);
        while(!q.empty()){
            int tmp=q.front();
            q.pop();
            for(int i=head[tmp];i!=-1;i=e[i].next){
                int tp=e[i].to;
                if(dis[tp]==-1&&e[i].cap){
                    dis[tp]=dis[tmp]+1;
                    q.push(tp);
                    if(tp==target)
                        return true;
                }
            }
        }
        return false;
    }
    
    int DFS(int u,int delta){
        if(u==target||delta==0)
            return delta;
        int f,flow=0;
        for(int& i=cur[u];i!=-1;i=e[i].next){
            if(dis[u]+1==dis[e[i].to] && (f=DFS(e[i].to,min(delta,e[i].cap))))
            {
                e[i].cap-=f;
                e[i^1].cap+=f;
                flow+=f;
                delta-=f;
                if(!delta)break;
            }
        }
        return flow;
    }
    
    int dinic(){
        int tmp=0,maxflow=0;
        while(BFS()){
            for(int i=src;i<=target;i++) cur[i]=head[i];
            while(tmp=DFS(src, INF))
                maxflow+=tmp;
        }
        return maxflow;
    }
}d;
namespace SPFA {
    int he[Vmax],ecnt;
    struct edge{
        int v,w,next;
    }e[Emax*2];
    int vis[Vmax];
    int dis[Vmax];
    int vcnt[Vmax];//记录每个点进队次数，用于判断是否出现负环
    bool inq[Vmax];
    vector<int> pre[Vmax];  //记录最短路中的上一个节点
    void init(){
        ecnt=0;
        memset(vcnt,0,sizeof(vcnt));
        memset(he,-1,sizeof(he));
        memset(inq, false, sizeof(inq));
    }
    //***注意双向加边
    void adde(int from,int to,int w){
        e[ecnt].v=to;
        e[ecnt].w=w;
        e[ecnt].next=he[from];
        he[from]=ecnt++;
    }
    bool SPFA(int n,int source){//n为顶点数 source为起点
        //return true表示无负环，反之亦然
        for (int i=0; i<=n; i++)
            dis[i]=INF;
        dis[source]=0;
        queue<int>q;
        q.push(source);inq[source]=true;
        
        while (!q.empty()) {
            int tmp=q.front();
            q.pop();inq[tmp]=false;
            
            //判断负环
            vcnt[tmp]++;
            if (vcnt[tmp]>=n) return false;
            
            for (int i=he[tmp]; i!=-1; i=e[i].next) {
                int w=e[i].w;
                int v=e[i].v;
                if (dis[tmp]+w<dis[v]) {
                    dis[v]=dis[tmp]+w;  //松弛操作
                    pre[v].clear();
                    pre[v].push_back(tmp);
                    if (!inq[v]) {
                        q.push(v);
                        inq[v]=true;
                    }
                }
                else if(dis[tmp] + w == dis[v]){
                    pre[v].push_back(tmp);
                }
            }
        }
        return true;
    }
    int get_ans(int n,int source,int destination){
        SPFA(n,source);
        return dis[destination];
    }
    void bfs(int n){
        memset(vis, 0, sizeof(vis));
        queue<int>q;
        q.push(n);
        vis[n] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0 ; i<pre[u].size(); i++) {
                int v = pre[u][i],w;
                if (v < u)  w = mp[make_pair(v, u)];
                else w = mp[make_pair(u, v)];
                d.adde(v, u, w);
                if (vis[v] == 0) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    
}


int main(){
    int T;
    scanf("%d",&T);
    while (T--) {
        mp.clear();
        int n,m;
        scanf("%d%d",&n,&m);
        SPFA::init();
        while (m--) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            if (u > v) swap(u, v);
            mp[make_pair(u, v)] = w;
            SPFA::adde(u, v, 1);
            SPFA::adde(v, u, 1);
        }
        SPFA::SPFA(n, 1);
        d.init(1, n);
        SPFA::bfs(n);
        cout<<d.dinic()<<"\n";
    }
}