网络流 费用流    发布于 2020-09-12   485人围观   0条评论


题解

我记得当年我在考场上做这个题的时候想出了很多奇奇怪怪的思路……反正就是不会处理上下界的问题,然后就这个题爆零了

实际上我已经想明白是上下界的费用流了,但是并不会有上下界的情况,所以只能想各种奇技淫巧。

所以,此题的正解就是无源汇有上下界的最小费用可行流。

对于无源汇的网络流问题,我们通常会设置虚拟源点S和虚拟汇点T。然后再在图上进行构建。

对于这个题也是一样,只是因为有上下界所以我们需要对图进行一下改进。

我们考虑一条边一定会流下界那么多的流,这样整张图的残量网络就构成了一个流量不平衡的图。我们需要构建另外一张流量不平衡的图,使得原始图和我们构建的图互补成为一张流量平衡的图。

我们考虑对于原图中进行统计,一个点每流出1流量,度数du[x]-1,流入1流量,度数du[x]+1。

如果最终一个点的度数<0(流出大于流入),则其在互补图中流入就要大于流出,这样我们就需要给他添加一些流出渠道来疏通这些多余的流入流量,这样就从点x向虚拟汇点T连一条容量为-du[x]的边。反之同理。

如果我们能找到一个流满足新加的边都满流,这个流在原图上的部分就是我们需要的与原图互补的附加流。

那么怎样找出一个新加的边都满流的流呢?可以发现假如存在这样的方案,这样的流一定是我们所建出的图的S-T最大流,所以跑S到T的最大流即可.如果最大流的大小等于S出发的所有边的流量上限之和(此时指向T的边也一定满流,因为这两部分边的流量上限之和相等),则说明此图是有可行流的.

在此题中也是如此,只是原图上的边加上了费用而已,而新加的边费用为0,直接跑有上下界最大费用可行流即可。

代码

#include <bits/stdc++.h>
using namespace std;
int T,S,E;
const int maxn = 205;
const int INF = 2e9;
struct edge{
    int fr,to,next,cap,dis;
}e[maxn<<3];
int h[maxn];
int cnt = 0;
void add(int u,int v,int cap,int d){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = cap;e[cnt].dis = d;e[cnt].next = h[u];h[u] = cnt++;
    e[cnt].fr
查看更多
费用流 网络流    发布于 2019-12-06   630人围观   0条评论


#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
const int INF = 1e9;
typedef long long ll;
ll a[maxn],b[maxn],c[maxn];
int p[maxn];
int d[maxn<<1],vis[maxn<<1];
deque<int>q;
int n;
struct edge{
    int to,next,cap,cost;
}e[maxn*maxn*2];
int S,T;
int h[maxn<<1];
int cnt = 0;
void add(int u,int v,int cap,int cost){
    e[cnt].to = v;e[cnt].cap = cap;e[cnt].cost = cost;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
bool spfa(int s,int t){
    for(int i = s;i <= t;++i){
        d[i] = -INF;
        vis[i] = 0;
    }
    d[t] = 0;
    vis[t] = 1;
    q.push_back(t);
    while(!q.empty()){
        int now = q.front();
        q.pop_front();
        vis[now] = 0;
        for(int i = h[now];i != -1;i = e[i].next){
            int v = e[i].to;
            if(e[i^1].cap && d[v] < d[now] - e[i].cost){
                d[v] = d[now] - e[i].cost;
                if(!vis[v]){
                    vis[v] = 1;
                    if(!q.empty() && d[q.front()] < d[v])q.push_front
查看更多
最短路 网络流 最小割    发布于 2019-07-23   520人围观   0条评论

题目大意

给出一张图,让你删除一些边,使得从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   355人围观   0条评论

题解

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

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

有攻击关系的点需要连一条流量为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   376人围观   0条评论

题目大意

有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   509人围观   0条评论

题目描述

给定正整数序列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   129人围观   0条评论

题解

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

我们只需要付出最小的代价破坏汽车(可以看作是道路)使得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   536人围观   0条评论

题解:

我们先来考虑一下我们在使用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   272人围观   0条评论

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   342人围观   0条评论

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

查看更多