BZOJ|[BZOJ]2095 二分答案 + 混合图欧拉回路判定
Submit: 1171 Solved: 405
[ Submit][ Status][ Discuss] Description YYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承受的最大风力最小的路线。
Input 输入：第一行为两个用空格隔开的整数n（2<=n<=1000），m(1<=m<=2000)，接下来读入m行由空格隔开的4个整数a，b（1<=a,b<=n,a<>b），c，d(1<=c,d<=1000)，表示第i+1行第i座桥连接小岛a和b，从a到b承受的风力为c，从b到a承受的风力为d。
Output 输出：如果无法完成减肥计划，则输出NIE，否则第一行输出承受风力的最大值（要使它最小)
Sample Input 4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
Sample Output 4
HINT
注意：通过桥为欧拉回路
【BZOJ|[BZOJ]2095 二分答案 + 混合图欧拉回路判定】
Source
HOME Back
通过网络流来判断混合图是否有欧拉回路是很经典的作法了...
首先说一下为什么是混合图. 让最大权值最小， 首相要想到二分. 我们二分这个边权. 然后遍历整个图将大于这个边权的删掉， 那么有些双向边就会变成单向边. 那么现在的问题就转化成了， 判断当前这个混合图(又有双向边又有单向边)是否有欧拉回路. 跑一边网络流即可.
如何用网络流判断混合图是否有欧拉路径:Click.
代码中二分删边之后没有判图是否连通， 按理来说是要用并查集去判连通性.
注意代码中千万不要用d数组表示度数， 因为题目中本身也有d数组...我死的很惨， 红了一页.
#include
#include
#include
#define clear(a) memset(a, 0, sizeof(a))
#define deeper(a) memset(a, -1 ,sizeof(a))
using namespace std;
const int maxn = 2005;
const int inf = 1e8;
queue q;
int n, m, num, S, T, ed, sum, ans;
int u[maxn], v[maxn], c[maxn], d[maxn], h[maxn], dis[maxn], de[maxn];
struct edge{ int v, nxt, c;
}e[1000005];
inline void add(int u, int v, int c){
e[++num].v = v, e[num].c = c, e[num].nxt = h[u], h[u] = num;
e[++num].v = u, e[num].c = 0, e[num].nxt = h[v], h[v] = num;
}
inline bool bfs(){
deeper(dis), dis[S] = 1, q.push(S);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = h[u];
i;
i = e[i].nxt){
int v = e[i].v;
if(dis[v] == -1 && e[i].c) dis[v] = dis[u] + 1, q.push(v);
}
}
return dis[T] != -1;
}
inline int dfs(int u, int a){
if(u == T) return a;
int flow = 0, f = 0;
for(int i = h[u];
i;
i = e[i].nxt){
int v = e[i].v;
if(dis[v] == dis[u] + 1 && e[i].c){
int x = min(e[i].c, a);
f = dfs(v, x);
e[i].c -= f, e[i ^ 1].c += f;
flow += f, a -= f;
if(!a) return flow;
}
}
if(!flow) dis[u] = -1;
return flow;
}
inline bool check(int mid){
num = 1, sum = 0, ans = 0;
clear(h), clear(de);
for(int i = 1;
i <= m;
++i){
if(c[i] <= mid) de[u[i]]--, de[v[i]]++;
if(d[i] <= mid) add(v[i], u[i], 1);
}
for(int i = 1;
i <= n;
++i)
if(de[i] > 0) sum += de[i] / 2, add(S, i, de[i] / 2);
else add(i, T, -de[i] / 2);
for(int i = 1;
i <= n;
++i) if(de[i] & 1) return false;
while(bfs()) ans += dfs(S, inf);
return ans == sum;
}
int main(){
scanf("%d%d", &n, &m);
S = 0, T = n + 1;
int lf = inf, rg = 0;
for(int i = 1;
i <= m;
++i){
scanf("%d%d%d%d", &u[i], &v[i], &c[i], &d[i]);
if(c[i] > d[i]) swap(c[i], d[i]), swap(u[i], v[i]);
lf = min(lf, c[i]), rg = max(rg, d[i]);
}
ed = rg;
while(lf <= rg){
int mid = (lf + rg) >> 1;
if(check(mid)) rg = mid - 1;
else lf = mid + 1;
}
if(lf == ed + 1) puts("NIE");
else printf("%d\n", lf);
return 0;
} 推荐阅读
- 1月尾，是2018年的十二分之一，陈先生自我独白
- 终极找 bug 大法 - 二分
- 算法|算法-二分查找
- 128
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- [Golang]力扣Leetcode—初级算法—排序和搜索—第一个错误的版本（二分查找）
- Go Rust 排序和二分搜索的对比
- 【BZOJ】4316:|【BZOJ】4316: 小C的独立集 静态仙人掌
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN