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

 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