【bzoj4519】[Cqoi2016]不同的最小割 分治+最小割
不同 最小 分治
2023-09-11 14:22:40 时间
题目描述
学过图论的同学都知道最小割的概念:对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点s,t不在同一个部分中,则称这个划分是关于s,t的割。对于带权图来说,将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量,而s,t的最小割指的是在关于s,t的割中容量最小的割。
而对冲刺NOI竞赛的选手而言,求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽,考虑有N个点的无向连通图中所有点对的最小割的容量,共能得到N(N−1)2个数值。
这些数值中互不相同的有多少个呢?这似乎是个有趣的问题。
输入
输入文件第一行包含两个数N,M,表示点数和边数。接下来M行,每行三个数u,v,w,表示点u和点v(从1开始标号)之间有条边权值是w。
1<=N<=850 1<=M<=8500 1<=W<=100000
输出
输出文件第一行为一个整数,表示个数。
样例输入
4 4
1 2 3
1 3 6
2 4 5
3 4 4
样例输出
3
题解
分治+最小割,同 bzoj2229 。
最后统计答案时把两点最小割取出来,去个重,求一下个数即可。
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> #define N 860 #define M 17010 using namespace std; queue<int> q; int n , head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N] , a[N] , tmp[N] , ans[N][N] , v[1000000] , tot; void add(int x , int y , int z) { to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = z , next[cnt] = head[y] , head[y] = cnt; } bool bfs() { int x , i; memset(dis , 0 , sizeof(dis)); while(!q.empty()) q.pop(); dis[s] = 1 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) { if(val[i] && !dis[to[i]]) { dis[to[i]] = dis[x] + 1; if(to[i] == t) return 1; q.push(to[i]); } } } return 0; } int dinic(int x , int low) { if(x == t) return low; int temp = low , i , k; for(i = head[x] ; i ; i = next[i]) { if(val[i] && dis[to[i]] == dis[x] + 1) { k = dinic(to[i] , min(temp , val[i])); if(!k) dis[to[i]] = 0; val[i] -= k , val[i ^ 1] += k; if(!(temp -= k)) break; } } return low - temp; } void solve(int l , int r) { if(l >= r) return; int i , j , sum = 0 , p1 , p2; for(i = 2 ; i <= cnt ; i += 2) val[i] = val[i ^ 1] = (val[i] + val[i ^ 1]) >> 1; s = a[l] , t = a[r]; while(bfs()) sum += dinic(s , 1 << 30); for(i = 1 ; i <= n ; i ++ ) if(dis[i]) for(j = 1 ; j <= n ; j ++ ) if(!dis[j]) ans[i][j] = ans[j][i] = min(ans[i][j] , sum); for(p1 = i = l , p2 = r ; i <= r ; i ++ ) { if(dis[a[i]]) tmp[p1 ++ ] = a[i]; else tmp[p2 -- ] = a[i]; } for(i = l ; i <= r ; i ++ ) a[i] = tmp[i]; solve(l , p2) , solve(p1 , r); } int main() { int m , i , j , x , y , z , ret = 0; scanf("%d%d" , &n , &m); while(m -- ) scanf("%d%d%d" , &x , &y , &z) , add(x , y , z); for(i = 1 ; i <= n ; i ++ ) a[i] = i; memset(ans , 0x7f , sizeof(ans)) , solve(1 , n); for(i = 1 ; i <= n ; i ++ ) for(j = i + 1 ; j <= n ; j ++ ) v[++tot] = ans[i][j]; sort(v + 1 , v + tot + 1); v[0] = -1 << 30; for(i = 1 ; i <= tot ; i ++ ) if(v[i] != v[i - 1]) ret ++ ; printf("%d\n" , ret); return 0; }
相关文章
- redis 中 set 和 hset 有什么不同,什么时候使用 hset 什么时候使用set?
- 不同shutdown命令的区别
- Qt——信号槽连接:基于字符串与基于函数的连接之间的不同
- 【K3s】第27篇 部署dashboard时不同k3s版本获取token的方式
- 科普干货|漫谈鸿蒙LiteOS-M与HUAWEI LiteOS内核的几大不同
- C语言宏定义技巧——多次包括头文件内容不同
- SQL、Linq、lamda表达式 同一功能不同写法
- 1481. 不同整数的最少数目-快速排序+贪心算法
- 长度为 3 的不同回文子序列-暴力求解加数组判断优化
- C++ 一个数组只有两个不同的数出现了奇数次,请找出这两个数
- 如何在C ++循环中生成不同的随机数?
- Java如何显示不同格式的日期?
- 编译解释两种方式只是翻译的时间不同
- 【python 数据分析】不同情况下的t检验、Wilcoxon符号秩检验、Wilcoxon秩和检验、卡方检验、Fisher检验
- FPGA 20个例程篇:1.不同按键控制不同LED亮灭