首页 > 代码库 > Barricade---hdu5889（最短路+网络流）
Barricade---hdu5889（最短路+网络流）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5889
题意：有n个点m条边，每条边的长度相同，我们可以默认为1，构成一个无向图；现在起点为1，终点为n，从起点到终点有很多路可走，现在已知每次走的都是最短路径；
现在要设置障碍，已知在每条边上设置障碍的代价wi, 为了让从起点到达终点一定能看到至少一个障碍，求建立障碍的最小代价；
思路：已知每次都会选择最短路径，所以我们可以把所有的最短路径所包含的边都找出来建立新的网络流图，然后求从起点到达终点的网络流即可；
参考题目hdu3416：http://www.cnblogs.com/zhengguiping--9876/p/5829830.html
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>#include<queue>#include<set>using namespace std;#define met(a, b) memset(a, b, sizeof(a))#define N 100005#define INF 0x3f3f3f3ftypedef long long LL;struct node{ int v, w, d, Next; node(int v_=0, int w_=0, int d_=0) : v(v_), w(w_), d(d_){}}e[N*4];vector<vector<node> >g;///存放原图；int n, vis[N];int dist[N];///spfa中的从起点到i的最短距离；int l[N];///Dinic中的分层int Head1[N], cnt1;void Add1(int u, int v, int w)///添加新的边；{ e[cnt1].v = v; e[cnt1].w = w; e[cnt1].Next = Head1[u]; Head1[u] = cnt1++;}void Init(){ g.clear(); g.resize(n+1); met(Head1, -1); cnt1 = 0; for(int i=0; i<=n; i++) { vis[i] = 0; dist[i] = INF; }}void spfa(){ dist[1] = 0; vis[1] = 1; queue<int>Q; Q.push(1); while(!Q.empty()) { int p = Q.front();Q.pop(); vis[p] = 0; for(int i=0, len=g[p].size(); i<len; i++) { int q = g[p][i].v; if(dist[q] > dist[p]+g[p][i].d) { dist[q] = dist[p]+g[p][i].d; if(!vis[q]) { vis[q] = 1; Q.push(q); } } } }}bool bfs(int s, int End){ met(l, 0); queue<int>Q; Q.push(s); l[s] = 1; while(!Q.empty()) { int u = Q.front();Q.pop(); if(u == End) return true; for(int i=Head1[u]; i!=-1; i=e[i].Next) { int v = e[i].v; if(!l[v] && e[i].w) { l[v] = l[u]+1; Q.push(v); } } } return false;}int dfs(int u, int MaxFlow, int End){ if(u == End)return MaxFlow; int uflow = 0; for(int j=Head1[u]; j!=-1; j=e[j].Next) { int v = e[j].v; if(l[v]==l[u]+1 && e[j].w) { int flow = min(e[j].w, MaxFlow-uflow); flow = dfs(v, flow, End); e[j].w -= flow; e[j^1].w += flow; uflow += flow; if(uflow == MaxFlow) break; } } if(uflow == 0) l[u] = 0; return uflow;}int Dinic(){ int MaxFlow = 0; while(bfs(1, n)) MaxFlow += dfs(1, INF, n); return MaxFlow;}int main(){ int T, m, u, w, v; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &m); Init(); for(int i=1; i<=m; i++) { scanf("%d %d %d", &u, &v, &w); g[u].push_back(node(v, w, 1)); g[v].push_back(node(u, w, 1)); } spfa();///更新dist for(int i=1; i<=n; i++) { for(int j=0, len=g[i].size(); j<len; j++) { int p = g[i][j].v; if(dist[p] == dist[i] + g[i][j].d)///说明从点i到达点p的路在最短路径上； { Add1(i, p, g[i][j].w);///建立新图； Add1(p, i, 0);///注意这里是0； } } } int ans = Dinic();///求最大流即可； printf("%d\n", ans); } return 0;}
Barricade---hdu5889（最短路+网络流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。