Tag-最小割

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

 2019-07-23 13:56:02 |  0 Comments  |  最短路 网络流 最小割

2019 Multi-University Training Contest 1 1005 Path 最小割+最短路

题目大意

给出一张图,让你删除一些边,使得从1到n的最短路变大,代价为删除边的长度。若本身1与n不连通则输出0。

题解

有人说dinic 会T炸,那应该是他们dinic板子不够优。

这题其实就是先求出1——n的所有最短路,以所有最短路为边建一张图,然后割掉一些边使得1与n不连通。

这是很明显的最小割模型……我们最小割的原图中的所有边的流量即为其原先的长度。

至于如何求所有最短路。

直接求出从1出发的单源最短路,然后遍历一遍所有边,检查当前的边是否是最短路上的边即可。

我寻思我用复杂度比较玄学的SPFA+dinic也过去了啊……而且是1A那种,怎么那么多人说会T炸呢?

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e4+5;
int T;
typedef long long ll;
const ll INF = 1e15;
struct Flow{
    struct edge{
        int to,next;
        ll cap;
    }e[maxn<<2];
    int h[maxn];
    int cur[maxn];
    int cnt;
    void init(){
        cnt = 0;
        memset(h,-1,sizeof(h));
 
 2019-07-03 17:41:17 |  0 Comments  |  网络流 最小割

洛谷P1344 [USACO4.4]追查坏牛奶Pollutant Control 基础最小割模型

题解

说实话这是一个水题……一眼看出来就是最小割模型……

我们只需要付出最小的代价破坏汽车(可以看作是道路)使得S和T不连通就行了。

于是我们连有向边,以损失为此边流量。建好图直接跑1到N的最小割就是了。这样最小损失就求出来了。

至于第二问,我们可以像第一问一样把边的流量改为1,然后再跑最小割。这是一定正确的,请自行证明。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = (num<<3) + (num<<1) + c - '0';
	return (flag ? -1 : 1) * num;
}
int S,T;
const int maxn = 55;
const int maxm = 1005;
const int INF = 1e9;
struct Flow{
	int h[maxn],cur[maxn];
	struct edge{
		int to,next,cap;
	}e[maxm<<1];
	int cnt;
	void add(int u,int v,int c){
		e[cnt].to = v;e[cnt].next = h[u];e[cnt].cap = c;
		h[u] = cnt++;
		return;
	}
	int d[maxn];
	bool BFS(int s,int t){
		queue<int>q;
		for(int i = s;i <= t;++i){
			d[i] = INF;
		}
		d[s] = 0;
		q.push(s);
		while(!q.empty()){
			int now = q.front();
			q.pop();
			for(int i = h[now];i != -1;i = e[i].next){
				int v = e[i].t
 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