[bzoj3130]:[Sdoi2013]费用流 – MXG's blog

[bzoj3130]:[Sdoi2013]费用流

[bzoj3130]:[Sdoi2013]费用流

Description

对于一张给定的运输网络,Alice先确定一个最大流,如果有多种解,Alice可以任选一种;之后Bob在每条边上分配单位花费(单位花费必须是非负实数),要求所有边的单位花费之和等于P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到,Bob在分配单位花费之前,已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小,而Bob希望总费用尽量大。我们想知道,如果两个人都执行最优策略,最大流的值和总费用分别为多少。


Hint

对于20%的测试数据:所有有向边的最大流量都是1。

对于100%的测试数据:N < = 100,M < = 1000。

对于l00%的测试数据:所有点的编号在I..N范围内。1 < = 每条边的最大流量 < = 50000。1 < = P < = 10。给定运输网络中不会有起点和终点相同的边。


Solution

样例是唬人的,Bob每次一定是将所有费用强加在最大的流的一条边上。
然后Alice要做的事情就是最小化最大流的一条边上的流
二分答案,实数二分,每次暴力dinic

复杂度是$O(n^2mlog50000)$


Code

#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

inline int read() {
    char c = getchar(); int x = 0;
    while(!isdigit(c)) c = getchar();
    do {
        x = x * 10 + (c ^ 48);
        c = getchar();
    } while(isdigit(c));
    return x;
}

const int N = 105;
const int M = 1029;
const double eps = 1e-5;
const int inf = 0x3f3f3f3f;
struct E {
    int nxt, to;
    double cap, flow;
}edg[M << 1];
int head[N], level[N];
int n, m, p, s, t, cnt = 1, qwq;
double l, r;
queue<int>q;

void add(int from, int to, int cap) {
    edg[++cnt].nxt = head[from]; edg[cnt].to = to;
    edg[cnt].cap = cap; edg[cnt].flow = 0;
    head[from] = cnt;
}

void build_edge(int u, int v, int c) {
    add(u, v, c); add(v, u, 0);
}

void init(double capflow) {
    for(int i = 1; i <= cnt; ++i) {
        edg[i].flow = 0;
        if(edg[i].cap > capflow) 
            edg[i].flow += edg[i].cap - capflow;
    }
}

bool bfs() {
    memset(level, 0, sizeof(level));
    level[s] = 1;
    q.push(s);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = head[u]; ~i; i = edg[i].nxt) {
            int v = edg[i].to;
            if(!level[v] && edg[i].flow < edg[i].cap) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t];
}

double dfs(int u, double a) {
    if(u == t || fabs(a) < eps) return a;
    double addflow = 0;
    for(int i = head[u]; ~i; i = edg[i].nxt) {
        int v = edg[i].to;
        if(fabs(edg[i].cap - edg[i].flow) > eps && level[v] == level[u] + 1) {
            double f = dfs(v, min(edg[i].cap - edg[i].flow, a));
            if(fabs(f) > eps) {
                a -= f; addflow += f;
                edg[i].flow += f; edg[i ^ 1].flow -= f;
                if(fabs(a) < eps) break;
            } else level[v] = -1;
        }
    }
    return addflow;
}

double dinic() {
    double res = 0;
    while(bfs()) res += dfs(s, inf);
    return res;
}

int main() {
    memset(head, -1, sizeof(head));
    n = read(), m = read(), p = read();
    for(int i = 1; i <= m; ++i) {
        int ta = read(), tb = read(), tc = read();
        build_edge(ta, tb, tc);
        qwq = max(qwq, tc);
    }
    s = 1, t = n;
    l = 0, r = qwq;
    double maxflow = dinic();
    while((r - l) > eps) {
        double mid = (r + l) / 2.0;
        init(mid);
        double curflow = dinic();
        if(fabs(curflow - maxflow) < eps) r = mid;
        else l = mid;
    }
    printf("%d\n%.4f", (int)maxflow, l * p);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒