解题报告 之 HDU5294 Tricks Device
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了解题报告 之 HDU5294 Tricks Device,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5607字,纯文字阅读大概需要9分钟。
内容图文
![解题报告 之 HDU5294 Tricks Device](/upload/InfoBanner/zyjiaocheng/1244/001356d91d8f431fba160d64c1067e17.jpg)
解题报告 之 HDU5294 Tricks Device
Description
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb Zhang.
Input
For each case,the first line must includes two integers, N(<=2000), M(<=60000). N is the total number of the chambers, M is the total number of the channels.
In the following M lines, every line must includes three numbers, and use ai、bi、li as channel i connecting chamber ai and bi(1<=ai,bi<=n), it costs li(0<li<=100) minute to pass channel i.
The entrance of the tomb is at the chamber one, the end of tomb is at the chamber N.
Output
Sample Input
8 9 1 2 2 2 3 2 2 4 1 3 5 3 4 5 4 5 8 1 1 6 2 6 7 5 7 8 1
Sample Output
2 6
![技术分享](/upload/getfiles/default/2022/11/10/20221110044853553.jpg)
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<deque> #include<vector> #include<utility> using namespace std; const int MAXN = 2510; const int MAXM = 300010; const int INF = 0x3f3f3f3f; struct Edge { int from, to, cap, next; }; Edge edge[MAXM]; Edge edge2[MAXM]; int head[MAXN]; int head2[MAXN]; int level[MAXN]; int dis1[MAXN], dis2[MAXN]; int src, des, cnt, cnt2; void SPFA(int *dis, int src,int n) { int inqueue[MAXN] = {0}; deque<int> q; dis[src] = 0; inqueue[src] = 1; q.push_front( src ); while(!q.empty()) { int u = q.front(); q.pop_front(); for(int i = head2[u]; i !=-1;i=edge2[i].next ) { int v = edge2[i].to; if(dis[v]>dis[u]+edge2[i].cap) { dis[v] = dis[u] + edge2[i].cap; if(!inqueue[v]) { if(!q.empty() && dis[v] > dis[q.front()]) q.push_front( v ); else q.push_back( v ); } } } } } void addedge( int from, int to, int cap ) { edge[cnt].from = from; edge[cnt].to = to; edge[cnt].cap = cap; edge[cnt].next = head[from]; head[from] = cnt++; swap( from, to ); edge[cnt].from = from; edge[cnt].to = to; edge[cnt].cap = 0; edge[cnt].next = head[from]; head[from] = cnt++; } void addedge2( int from, int to, int cap ) { edge2[cnt2].from = from; edge2[cnt2].to = to; edge2[cnt2].cap = cap; edge2[cnt2].next = head2[from]; head2[from] = cnt2++; } bool bfs() { memset( level, -1, sizeof level ); queue<int> q; while(!q.empty()) q.pop(); level[src] = 0; q.push( src ); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(edge[i].cap > 0 && level[v] == -1) { level[v] = level[u] + 1; q.push( v ); if(v == des) return level[des] != -1; } } } return level[des] != -1; } int dfs( int u, int f ) { if(u == des) return f; int tem; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(edge[i].cap > 0 && level[v] == level[u] + 1) { tem = dfs( v, min( f, edge[i].cap ) ); if(tem > 0) { edge[i].cap -= tem; edge[i ^ 1].cap += tem; return tem; } } } level[u] = -1; return 0; } int Dinic() { int ans = 0, tem = 0; while(bfs()) { tem = dfs( src, INF ); if(tem > 0) ans += tem; } return ans; } int main() { int n, m; while(cin >> n >> m) { cnt = cnt2 = 0; src = 1; des = n; memset( head, -1, sizeof head ); memset( head2, -1, sizeof head2 ); memset( dis1, INF, sizeof dis1 ); memset( dis2, INF, sizeof dis2 ); int a, b, c; for(int i = 1; i <= m; i++) { scanf( "%d%d%d",&a,&b,&c); addedge2( a, b, c ); addedge2( b, a, c ); } SPFA( dis1, 1, n ); SPFA( dis2, n, n ); for(int i = 1; i <= n; i++) //重构图 { for(int j = head2[i]; j != -1; j = edge2[j].next) { int v = edge2[j].to; if(dis1[i] + edge2[j].cap + dis2[v] == dis1[n]) { addedge( i, v, 1 ); edge2[j].cap = 1; } else { edge2[j].cap = INF; } } } memset( dis1, INF, sizeof dis1 ); SPFA(dis1, 1, n ); cout << Dinic()<<" " << m-dis1[n]<<endl; } return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/maxichu/article/details/47699869
内容总结
以上是互联网集市为您收集整理的解题报告 之 HDU5294 Tricks Device全部内容,希望文章能够帮你解决解题报告 之 HDU5294 Tricks Device所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。