【题目来源】https://www.acwing.com/problem/content/2279/【题目描述】农夫约翰正在制造一台新的挤奶机并希望对这件事进行严格保密。他将挤奶机藏在了农场的深处使他能够在不被发现的情况下进行这项任务。在机器制造的过程中他要在牛棚和挤奶机之间一共进行 T 次往返。他有一个秘密通道只能在返程时使用。农场由 N 个地标编号 1∼N组成这些地标由 P 条双向道路编号 1∼P连接。每条道路的长度为正且不超过 10^6。多条道路可能连接同一对地标。为了尽可能的减少自己被发现的可能性农场中的任何一条道路都最多只能使用一次并且他应该尝试使用尽可能短的道路。帮助约翰从牛棚地标 1到达秘密挤奶机地标 N总共 T 次。找到他必须使用的最长的单个道路的最小可能长度。请注意目标是最小化所使用的最长道路的长度而不是最小化所有被使用道路的长度之和。保证约翰可以在不走重复道路的情况下完成 T 次行程。【输入格式】第一行包含三个整数 NPT。接下来 P 行每行包含三个整数 AiBiLi表示地标 Ai 和 Bi 之间存在一条长度为 Li 的道路。【输出格式】输出一个整数表示约翰必须使用的最长的单个道路的最小可能长度。【输入样例】7 9 21 2 22 3 53 7 51 4 14 3 14 5 75 7 11 6 36 7 3【输出样例】5【数据范围】1≤T≤2002≤N≤2001≤P≤400001≤Ai,Bi≤N1≤Li≤10^6【算法分析】● Dinic算法https://blog.csdn.net/hnjzsyjyj/article/details/161317988● 本题二分思想简述1. 二分对象枚举路径中允许出现的最大边权记为 mid目标找到满足条件的最小 mid。2. 判定规则1若只使用边权 ≤ mid 的边能找出至少 k 条边不相交路径最大流 ≥ k说明 mid 可行尝试缩小范围令 ri mid。2若无法凑出 k 条路径说明当前限制过严需要放大边权上限令 le mid 1。3. 收敛结果二分循环结束后le ri即为所有合法方案里路径最大边权的最小值。【算法代码】#include bits/stdc.h using namespace std; typedef long long LL; const int INF0x3f3f3f3f; const int N2e25,M8e45; int h[N],e[M],c[M],f[M],ne[M],idx; int q[N],d[N],cur[N]; int n,m,k,S,T; void add(int a,int b,int w) { e[idx]b,c[idx]w,ne[idx]h[a],h[a]idx; e[idx]a,c[idx]w,ne[idx]h[b],h[b]idx; } bool bfs() { memset(d,-1,sizeof d); int hh0,tt0; q[0]S,d[S]0; while(hhtt) { int uq[hh]; for(int ih[u]; ~i; ine[i]) { int ve[i]; if(d[v]-1 f[i]) { d[v]d[u]1; q[tt]v; } } } return d[T]!-1; } int dfs(int u,int lim) { if(uT) return lim; int flow0; for(int icur[u]; ~i flowlim; ine[i]) { cur[u]i; int ve[i]; if(d[v]d[u]1 f[i]) { int tdfs(v,min(f[i],lim-flow)); if(!t) d[v]-1; f[i]-t,f[i^1]t,flowt; } } return flow; } LL dinic() { LL r0,flow0; while(bfs()) { //0~T for(int i0; iT; i) cur[i]h[i]; while(flowdfs(S,INF)) rflow; } return r; } bool check(int mid) { for(int i0; iidx; i) { if(c[i]mid) f[i]0; else f[i]1; } return dinic()k; } int main() { memset(h,-1,sizeof h); cinnmk; S1,Tn; while(m--) { int a,b,c; cinabc; add(a,b,c); } int le1,ri1e6; while(leri) { int midleri1; if(check(mid)) rimid; else lemid1; } coutriendl; return 0; } /* in: 7 9 2 1 2 2 2 3 5 3 7 5 1 4 1 4 3 1 4 5 7 5 7 1 1 6 3 6 7 3 out: 5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161492982https://blog.csdn.net/hnjzsyjyj/article/details/161317988https://blog.csdn.net/hnjzsyjyj/article/details/161471616https://www.acwing.com/solution/content/125224/
AcWing 2277：秘密挤奶机 ← Dinic算法 + 二分 + 最大流判定
【题目来源】https://www.acwing.com/problem/content/2279/【题目描述】农夫约翰正在制造一台新的挤奶机并希望对这件事进行严格保密。他将挤奶机藏在了农场的深处使他能够在不被发现的情况下进行这项任务。在机器制造的过程中他要在牛棚和挤奶机之间一共进行 T 次往返。他有一个秘密通道只能在返程时使用。农场由 N 个地标编号 1∼N组成这些地标由 P 条双向道路编号 1∼P连接。每条道路的长度为正且不超过 10^6。多条道路可能连接同一对地标。为了尽可能的减少自己被发现的可能性农场中的任何一条道路都最多只能使用一次并且他应该尝试使用尽可能短的道路。帮助约翰从牛棚地标 1到达秘密挤奶机地标 N总共 T 次。找到他必须使用的最长的单个道路的最小可能长度。请注意目标是最小化所使用的最长道路的长度而不是最小化所有被使用道路的长度之和。保证约翰可以在不走重复道路的情况下完成 T 次行程。【输入格式】第一行包含三个整数 NPT。接下来 P 行每行包含三个整数 AiBiLi表示地标 Ai 和 Bi 之间存在一条长度为 Li 的道路。【输出格式】输出一个整数表示约翰必须使用的最长的单个道路的最小可能长度。【输入样例】7 9 21 2 22 3 53 7 51 4 14 3 14 5 75 7 11 6 36 7 3【输出样例】5【数据范围】1≤T≤2002≤N≤2001≤P≤400001≤Ai,Bi≤N1≤Li≤10^6【算法分析】● Dinic算法https://blog.csdn.net/hnjzsyjyj/article/details/161317988● 本题二分思想简述1. 二分对象枚举路径中允许出现的最大边权记为 mid目标找到满足条件的最小 mid。2. 判定规则1若只使用边权 ≤ mid 的边能找出至少 k 条边不相交路径最大流 ≥ k说明 mid 可行尝试缩小范围令 ri mid。2若无法凑出 k 条路径说明当前限制过严需要放大边权上限令 le mid 1。3. 收敛结果二分循环结束后le ri即为所有合法方案里路径最大边权的最小值。【算法代码】#include bits/stdc.h using namespace std; typedef long long LL; const int INF0x3f3f3f3f; const int N2e25,M8e45; int h[N],e[M],c[M],f[M],ne[M],idx; int q[N],d[N],cur[N]; int n,m,k,S,T; void add(int a,int b,int w) { e[idx]b,c[idx]w,ne[idx]h[a],h[a]idx; e[idx]a,c[idx]w,ne[idx]h[b],h[b]idx; } bool bfs() { memset(d,-1,sizeof d); int hh0,tt0; q[0]S,d[S]0; while(hhtt) { int uq[hh]; for(int ih[u]; ~i; ine[i]) { int ve[i]; if(d[v]-1 f[i]) { d[v]d[u]1; q[tt]v; } } } return d[T]!-1; } int dfs(int u,int lim) { if(uT) return lim; int flow0; for(int icur[u]; ~i flowlim; ine[i]) { cur[u]i; int ve[i]; if(d[v]d[u]1 f[i]) { int tdfs(v,min(f[i],lim-flow)); if(!t) d[v]-1; f[i]-t,f[i^1]t,flowt; } } return flow; } LL dinic() { LL r0,flow0; while(bfs()) { //0~T for(int i0; iT; i) cur[i]h[i]; while(flowdfs(S,INF)) rflow; } return r; } bool check(int mid) { for(int i0; iidx; i) { if(c[i]mid) f[i]0; else f[i]1; } return dinic()k; } int main() { memset(h,-1,sizeof h); cinnmk; S1,Tn; while(m--) { int a,b,c; cinabc; add(a,b,c); } int le1,ri1e6; while(leri) { int midleri1; if(check(mid)) rimid; else lemid1; } coutriendl; return 0; } /* in: 7 9 2 1 2 2 2 3 5 3 7 5 1 4 1 4 3 1 4 5 7 5 7 1 1 6 3 6 7 3 out: 5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161492982https://blog.csdn.net/hnjzsyjyj/article/details/161317988https://blog.csdn.net/hnjzsyjyj/article/details/161471616https://www.acwing.com/solution/content/125224/
