Tag-网络流

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

 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>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5
 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()) == '
 2017-02-18 21:33:58 |  0 Comments  |  网络流 最大流

SDOI2013费用流

传送门:bzoj 3130

然后我估计这就是SDOI 喜欢出的网络流类型……

可别被题目名称误导了,这道题不是真的费用流(对对对它是假的费用流)……
这题真的只是最大流……
第一问就不说了,裸的Dinic,直接一边跑就行了。至于第二问,我们注意到,由于费用是边的实际流量乘费用,所以Bob依据自己的最优策略,一定会把所有的费用都压在实际流量最大的那条边上(这是显然的)。
那么作为Alice的最优策略,我们肯定是想要最大的费用最小,那么这提示够多了吧……
什么?还不够?看看费用的计算方式,也就是说我们只要让最大流量的边的实际流量尽量小就行了。
所以此题二分是正解……(SDOI2015也有二分网络流,这似乎是SDOI特别喜欢考的)
至于check函数的书写,那就是我们二分最大流量的边的实际流量,跑dinic,看最大流的大小是否和第一问一致。如果一致就继续往小二分,如果不一致就继续往大二分。最后输出二分的最终答案ans(我代码里是mid)*p就是第二问的答案
二分网络流的话建议还是把dinic写在struct结构体里面,初始化比较方便。
注意实数二分!!!

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
queue<int>q;
const int maxn = 105;
const int maxm = 1005;
const double INF = 100000007;
int n,m;double p;
int a,b;double c;
int S,T;
double ans1,ans2;
double l = 0;
double r = 50000,mid;
int cs = 50;
struct dinic_slove{
    struct edge{
        int fr,to,next;
        double cap; 
    }e[maxm<<3];
    int cnt;
    void init(){
        cnt = 0;
        return;
    }
    int
Title - Artist
0:00