icontofig | 发布于 2017-02-18 21:33:58 | 阅读量 190 | 网络流 最大流
发布于 2017-02-18 21:33:58 | 网络流 最大流

传送门: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 h[maxn],d[maxn],cur[maxn];
    void add(int u,int v,double c){
        e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = c;e[cnt].next = h[u];
        h[u] = cnt++;
    }
    bool BFS(){
        memset(d,-1,sizeof(d));
        d[S] = 0;
        q.push(S);
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for(int i = h[x];i != -1;i = e[i].next){
                int v = e[i].to;
                if(e[i].cap > 0 && d[v] == -1){
                    d[v] = d[x] + 1;
                    q.push(v);
                }
            }
        }
        if(d[T] == -1)return false;
        return true;
    }
    double dfs(int x,double a){
        if(x == T || a == 0)return a;
        double flow = 0;
        for(int& i = cur[x];i != -1;i = e[i].next){
            int v = e[i].to;
            if(e[i].cap > 0 && d[v] == d[x] + 1){
                double r = min(e[i].cap,a - flow);
                r = dfs(v,r);
                flow += r;
                e[i].cap -= r;
                e[i^1].cap += r;
            }
        }
        return flow;
    }
    double dinic(int s,int t){
        double flow = 0;
        while(BFS()){
            for(int i = s;i <= t;++i)cur[i] = h[i];
            flow += dfs(s,INF);
        }
        return flow;
    }
}dc,dc1;
void init(){
    dc.init();
    memset(dc.h,-1,sizeof(dc.h));
    memset(dc1.h,-1,sizeof(dc1.h));
    scanf("%d%d%lf",&n,&m,&p);
    for(int i = 1;i <= m;++i){
        scanf("%d%d%lf",&a,&b,&c);
        dc.add(a,b,c);dc.add(b,a,0);
        dc1.add(a,b,c);dc1.add(b,a,0);
    }
    S = 1;T = n;
}
bool check(double op){
    for(int i = 0;i < dc.cnt;i++)
        dc.e[i].cap = min(dc.e[i].cap,op);
    double u = 0;
    u = dc.dinic(S,T);
    if(u == ans1)return true;
    else return false;
}
int main(){
    init();
    ans1 = dc.dinic(S,T);
    printf("%d\n",(int)ans1);//第一问的解 
    while(cs > 0){//实数二分 
        dc = dc1;
        mid = (l + r) / 2;
        if(check(mid))
            r = mid;
        else l = mid;
        cs--;
    }
    ans2 = mid * p;
    printf("%.4lf\n",ans2);//第二问的解 
    return 0;
}
​

内容更新于: 2018-12-26 10:20:01
链接地址: http://blog.leanote.com/post/icontofig/f3c4689432df

上一篇: Codeforce Round #398 div.2 C ----767C

下一篇: codeforces 762A 模拟……

190 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航