Tag-费用流

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

 2020-09-12 15:19:46 |  0 Comments  |  网络流 费用流

CSP201812-05 管道清洁


题解

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

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

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

对于无源汇的网络流问题,我们通常会设置虚拟源点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 08:04:34 |  0 Comments  |  费用流 网络流

费用流zkw费用流(类似dinic)模板


#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-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 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
Title - Artist
0:00