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-15 17:15:53 |  0 Comments  |  网络流

骑士共存问题 [网络流24题] 二分图最大独立集

题解

很明显能看出来同色的格子之间是不会相互攻击的。

于是我们就可以把这张图分成一张二分图了,然后建边跑最大流。

有攻击关系的点需要连一条流量为1的边。

不过值得注意的是,要优化建边方法,不然会超时。

既然是二分图,我们考虑黄色格子代表的点与S连边,红色格子代表的点与T连边,在考虑攻击关系的时候,只从黄色格子连向红色格子就可以了(因为互相攻击,所以是等价的,当然与上述方案完全反过来建边也可以)。

我们要求的是最多的共存骑士,所以是明显的二分图最大独立集的问题,求出的最大流相当于一个最小割,用总数n*n-m再减去这个最小割就是最大独立集的最后剩余的数目。

代码

#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;
}
const int maxn = 205;
struct edge{
    int to,next,cap;
}e[maxn*maxn * 16];
int cnt = 0;
int h[maxn*maxn];
void add(int u,int v,int c){
    e[cnt].to = v;e[cnt].cap = c;e[cnt].next = h[u];
    h[u] = cnt++;
    return;
}
int d[maxn*maxn];
const int INF = 1e9;
bool BFS(int s,int t){
    for(int i = s;i <= t;++i){
        d[i] = INF;
    }
    d[s] = 0;
    queue<int>q;
   
 2019-07-13 19:09:19 |  0 Comments  |  最短路 二分 离散化 网络流 最大流

BAPC18 I In Case of an Invasion,Please... 最短路+离散化+二分+最大流

题目大意

有n个居民点,m条双向有权路径,和s个避难所。每个居民点有pi个居民,每个避难所的容量为Ci。

现在求能够让所有人避难的最少的需要的时间。

题解

我们如果有一个时间,那么我们该如何判断在这个时间内能不能安置所有居民呢?

很简单就能想到,这是一个利用最大流判断是否存在可行流的问题。

建立从源点s到每个居民点的容量为pi的有向边,从每个居民点到每个避难所容量为+∞的有向边,从每个避难所到汇点t容量为ci的有向边。

然后建完图直接跑最大流,判断最大流的流量是否等于所有的居民人数总和即可。

那这个时间我们该如何去求?

答案是可以二分。

二分出一个答案时间,然后检验这个时间下能否将所有人安置好。当然在建立居民点到避难所的有向边的时候应当考虑该居民点到该避难所的时间会不会大于当前给出的答案时间,若是小于等于则加入此边,否则不加入此边。

至于离散化,是一个能够优化常数的做法。就是预处理所有避难所到所有居民点的距离,并且装入一个数组,并对数组从小到大排序。然后直接枚举数组下标获取答案时间。

这样做是正确的,因为最终答案一定是某个居民点到某个避难所的时间,而不会有多余(这是很显然的,请读者思考)。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
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 n,m;
const int maxn = 2e5+25;
const int max
 2019-07-07 11:01:45 |  0 Comments  |  网络流 最大流

网络流24题 之 最长不下降子序列问题 洛谷P2766 分层图

题目描述

给定正整数序列x1,...,xn 。

(1)计算其最长不下降子序列的长度s。

(2)计算从给定的序列中最多可取出多少个长度为s的不下降子序列。

(3)如果允许在取出的序列中多次使用x1和xn,则从给定序列中最多可取出多少个长度为s的不下降子序列。

编程任务:

设计有效算法完成(1)(2)(3)提出的计算任务。

输入输出格式

输入格式:

第1 行有1个正整数n,表示给定序列的长度。接下来的1 行有n(n ≤ 500)个正整数n:x1, ..., xn。

输出格式:

第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的不下降子序列个数。

样例输入

4
3 6 2 5

样例输出

2
2
3

题解

此题是经典的网络流24题之一。

对第一问,我们直接写O(n2)的DP即可,最长不下降子序列的DP转移方程不再给出,可以参考代码。

其实最长不下降子序列也是有O(nlogn)算法的,通常来说那种算法更优,不过在本题中并不适用,原因在于此题的后两问。

首先看第二问,要我们求出这个序列中能取出多少个长度为s(最长)的子序列?

很明显如果如同导弹拦截(最长不下降子序列的基础题)一样不断求最长不下降子序列是有可能超时的?

我们可以考虑使用最大流模型。

让dp值为1的点连向设置的源点S,dp值为s的店连向设置的源点T。

然后我们可以根据O(n2)DP的转移方程给图来建边,做成一个以到当前节点为止的最长不下降子序列长度分层的分层图。

这就是为什么不用O(nlogn)的算法的原因了。

不过我一开始还WA了,我还在想为啥……

结果因为我没写限流……简直真的跟zz一样。

限流的写法就是每个点拆成入点和出点,入点向出点连一条流量为1的边代表这个点上的数只能选取1次。然后对应出点-入点建流量为1的边。

如此第三问就是把S到1的入点,1的入点到1的出点的流量改为INF。而对于第n个点,如果dp值为s,则n的入点向n的出点、n的出点向T的流量改为INF就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c
 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-24 16:33:29 |  0 Comments  |  网络流 费用流 最大流

HDU5352 MZL's City

Description

MZL is an active girl who has her own country.

Her big country has N cities numbered from 1 to N.She has controled the country for so long and she only remebered that there was a big earthquake M years ago,which made all the roads between the cities destroyed and all the city became broken.She also remebered that exactly one of the following things happened every recent M years:

1.She rebuild some cities that are connected with X directly and indirectly.Notice that if a city was rebuilt that it will never be broken again.

2.There is a bidirectional road between city X and city Y built.

3.There is a earthquake happened and some roads were destroyed.

She forgot the exactly cities that were rebuilt,but she only knew that no more than K cities were rebuilt in one year.Now she only want to know the maximal number of cities that could be rebuilt.At the same time she want you to tell her the smallest lexicographically plan under the best answer.Notice that 8 2 1 is smaller than 10 0 1.

I

 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

 2019-02-14 09:39:19 |  0 Comments  |  网络流 费用流

BZOJ 1937 Mst最小生成树

Description

Input

第一行为N、M,其中 表示顶点的数目, 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行,每行三个整数Ui,Vi,Wi,表示顶点Ui与Vi之间有一条边,其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行,每行两个整数Xi、Yi,表示顶点Xi与Yi之间的边是T的一条边。

Output

输出最小权值

Sample Input

6 9
1 2 2
1 3 2
2 3 3
3 4 3
1 5 1
2 6 3
4 5 4
4 6 7
5 6 6
1 3
2 3
3 4
4 5
4 6

Sample Output

8

【样例说明】 边(4,6)的权由7修改为3,代价为4
边(1,2)的权由2修改为3,代价为1
边(1,5)的权由1修改为4,代价为3
所以总代价为4+1+3=8
修改方案不唯一。

HINT

1<=n<=50,1<=m<=800,1<=wi<=1000
n-->点数..m-->边数..wi--->边权


题解

这道题的题意是要求修改一些边的权值使得给出的树成为这个图的最小生成树,求最小代价。
注意到我们只可能增大非树边,减小树边。

那么对于一个树边ii和一个可能影响到最小生成树的非树边jj,我们一定要满足如下条件:
widiwj+djwi−di≤wj+dj
移项,即
wiwjdi+djwi−wj≤di+dj
其中d表示我们对于边的改动值(一定非负)
这样就可以转化成二分图最小顶标和来做。
我们把边看成点,两原边边权之差作为新点之间的边权,跑一边KM或者最小费用最大流就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5+5,INF=1e9;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c ==
 2018-12-26 10:18:42 |  0 Comments  |  网络流 tarjan 最大流

NOI2009 植物大战僵尸(最大权闭合子图、联通量处理)

题目描述


输入格式

输出格式

仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。

样例输入

3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0​

样例输出

25​

数据范围及提示

在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。
一个方案为,首先进攻P1,1, P0,1,此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护,所以无法攻击第2行中的任何植物。

【大致数据规模】

约20%的数据满足1 ≤ N, M ≤ 5; 约40%的数据满足1 ≤ N, M ≤ 10; 约100%的数据满足1 ≤ N ≤ 20,1 ≤ M ≤ 30,-10000 ≤ Score ≤ 10000 。


题解

首先注意到,由于僵尸是从右侧开始走的,所以同一行内右侧植物可以认为是保护左侧一个植物的,在保护关系加边的时候可以加上这类边。
很好想,我们注意到如果把植物间的保护关系建出图,那么就可以发现,其实就是个最大权闭合子图(相当于最小割)的问题,不过形成环的植物们都是无敌的,所以可以用tarjan或者topsort求出环,然后把环上的点全部删掉,剩下的跑最大权闭合子图就行了。

网络流建图方式:

把剩下的点分为两类: score大于零的:从源点S向此点连边,流量为score
score小于零的:从此点向汇点T连边,流量为-score
然后每个点向自己保护的点连一条反向边,流量为INF
最大权闭合子图的求法:跟最小割一样,把剩下的点里面正的score全加起来,减去跑的dinic返回的值(最小割),就是答案。当然此处要和0取较大值。

代码


#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == '
Title - Artist
0:00