首页 > 代码库 > HDU 5889 (最短路+网络流)
HDU 5889 (最短路+网络流)
Barricade
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1117 Accepted Submission(s): 340
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.
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
14 41 2 12 4 23 1 34 3 4
Sample Output
4
最短路+网络流。
先一遍bfs找到最短路,再一次bfs找到最短路上的点,通过dis[i]+1 = dis[u]来找,然后跑一遍Dinic。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 const int maxn = 1005; 9 const int inf = 0x3f3f3f3f; 10 int n,m; 11 int g[maxn][maxn]; 12 int vis[maxn]; 13 int dis[maxn]; 14 struct edge 15 { 16 int to; 17 int cap; 18 int rev; 19 }; 20 vector<edge> gg[maxn]; 21 int level[maxn]; 22 int it[maxn]; 23 void add(int from,int to,int cap) 24 { 25 edge cur; 26 cur.to = to; 27 cur.cap = cap; 28 cur.rev = gg[to].size(); 29 gg[from].push_back(cur); 30 cur.to = from; 31 cur.cap = 0; 32 cur.rev = gg[from].size()-1; 33 gg[to].push_back(cur); 34 } 35 36 void bfs(int s) 37 { 38 memset(level,-1,sizeof(level)); 39 queue<int> q; 40 level[s] = 0; 41 q.push(s); 42 while(!q.empty()) 43 { 44 int v = q.front(); q.pop(); 45 for(int i=0;i<gg[v].size();i++) 46 { 47 edge &e = gg[v][i]; 48 if(e.cap>0&&level[e.to]<0) 49 { 50 level[e.to] = level[v]+1; 51 q.push(e.to); 52 } 53 } 54 } 55 } 56 int dfs(int v,int t,int f) 57 { 58 if(v==t) return f; 59 for(int &i=it[v];i<gg[v].size();i++) 60 { 61 edge &e = gg[v][i]; 62 if(e.cap>0&&level[v]<level[e.to]) 63 { 64 int d = dfs(e.to,t,min(f,e.cap)); 65 if(d>0) 66 { 67 e.cap -= d; 68 gg[e.to][e.rev].cap += d; 69 return d; 70 } 71 } 72 } 73 return 0; 74 } 75 int max_flow(int s,int t) 76 { 77 int flow = 0; 78 for(;;) 79 { 80 bfs(s); 81 if(level[t]<0) return flow; 82 memset(it,0,sizeof(it)); 83 int f; 84 while((f=dfs(s,t,inf))>0) flow += f; 85 } 86 } 87 bool bfs1() 88 { 89 queue<int> q; 90 memset(vis,0,sizeof(vis)); 91 memset(dis,inf,sizeof(dis)); 92 vis[1] = 1; 93 dis[1] = 0; 94 q.push(1); 95 while(!q.empty()) 96 { 97 int cur = q.front();q.pop(); 98 if(cur==n) return true; 99 for(int i=1;i<=n;i++)100 {101 if(cur==i) continue;102 if(!vis[i]&&g[cur][i]!=-1)103 {104 vis[i] = 1;105 dis[i] = dis[cur]+1;106 q.push(i);107 }108 }109 }110 return false;111 }112 void bfs2()113 {114 queue<int> q;115 memset(vis,0,sizeof(vis));116 vis[n] = 1;117 q.push(n);118 while(!q.empty())119 {120 int cur = q.front();q.pop();121 for(int i=1;i<=n;i++)122 {123 if(cur==i) continue;124 if(g[cur][i]==-1) continue;125 if(dis[i]+1==dis[cur])126 {127 add(i,cur,g[i][cur]);128 if(!vis[i])129 {130 vis[i] = 1;131 q.push(i);132 }133 }134 }135 }136 }137 int main()138 {139 int T;cin>>T;140 while(T--)141 {142 scanf("%d %d",&n,&m);143 int u,v,w;144 memset(g,-1,sizeof(g));145 for(int i=0;i<maxn;i++) gg[i].clear();146 for(int i=1;i<=m;i++)147 {148 scanf("%d %d %d",&u,&v,&w);149 g[u][v] = w;150 g[v][u] = w;151 }152 int ans = 0;153 bfs1();154 bfs2();155 ans = max_flow(1,n);156 printf("%d\n",ans);157 }158 return 0;159 }
HDU 5889 (最短路+网络流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。