Tag-最小割

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-04-27 22:35:58 |  0 Comments  |  最小割 网络流

BZOJ 2561 最小生成树(最小割模型)

题解:

我们先来考虑一下我们在使用kruskal算法的时候是怎么生成最小生成树的。

Kruskal算法是一种贪心算法,每次选择边权最小的一条边,检测一下两个端点是否都在一个并查集里,如果不是就加上这一条边,代表最小生成树选择这一条边。

于是这便是此题的关键,如果想要让新加进去的边可能出现在最小生成树中,那么在所有边权小于新边的边集中,就不能有一个子集使得新边的u和v连通。

如果有这样的边集,我们就要通过删边去破坏掉,而且使得破坏掉的边尽可能的少。

诶这不是完美契合最小割模型吗……可是这数据范围……

放心,dinic能顶得住……网络流的复杂度从来都是玄学,这话可不是假的……

于是对于最小生成树,我们就将所有的小于新边权值的边选出来建一张图,每条正向边的容量均为1,求出u,v之间的最小割,就是求出u,v之间的最大流,就可以得出最小生成树部分的答案。

对于最大生成树,其实和最小生成树类似,类比一下就可以了。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2e4+5;
const int maxm = 2e5+5;
struct edge{
    int fr,to,next,cap;
}e[maxm<<3];
int cnt = 0;
int h[maxn];
int cur[maxn],d[maxn];
const int INF = 1e9;
struct edge2{
    int fr,to,dis;
}e2[maxm];
int n,m;
/*
bool cmp(edge2 a,edge2 b){
    return a.dis < b.dis;
}//其实不用排序
*/
void add(int u,int v,int c){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = c;
    e[cnt].next = h[u];h[u] = cnt++;
    e[cnt].fr = v;e[cnt].to = u;e[cnt].cap 
 2019-02-14 10:43:38 |  0 Comments  |  网络流 最小割 最短路

BUPT校内训练 & HDU 5294 最短路&最小割

Description

Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
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

Title - Artist
0:00