题解：P3305 [SDOI2013] 费用流

· · 题解

题意

就是普通网络流，然后要在网络流的几条边上加一个费用（所有边的费用加起来等于 P），然后要使得每条边的实际流量乘每条边的费用之和最大。

看起来是不是很像费用流。

思路

其实这题跟费用流喵关系没有。

当看到 Bob 希望总费用尽量大时，你可能想问，每条边赋的费用有那么多种情况，总不可能一一枚举吧。

其实这里可以采用贪心的思想。我们注意到网络流上每条路径中的各个边的实际流量一致，那么为了使得费用最大，我们肯定要把实际流量最大的路径的费用设为 P（你也可以理解为除了这条路径，其他路径都免费）。

为什么要这样做呢？一个不太严谨但显然的证明如下：

如果你把实际流量最大的路径的费用设为 P，总费用就是：

f_{max} \times P

而如果你要赋其他路径，那费用就是：

f_1 \times P_1+f_2 \times P_2 +······+ f_n \times P_n

但你这除了 f_{max}，其他路径的实际流量加的费用，不完全可以用 f_{max} 替代吗？

所以这样的总费用就是最大的。

求最大？那自然而然的想到了二分。

注意到流量最大值可能不是整数，于是使用实数二分。

记得每次跑完网络流后要重新建图。

代码

主要的思路上面已经讲过，代码中就不多加赘述。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
const double inf=1e18;
const double eps=1e-6;
int n,m,s,t;
double p,maxm=-inf,ans;
int u[maxn],v[maxn];
double w[maxn];
struct node{
    int to,next;
    double w;
}e[2*maxn];
int head[maxn],tot=1;
void add(int u,int v,double w){
    e[++tot].to=v;
    e[tot].next=head[u];
    e[tot].w=w;
    head[u]=tot;
}
int dep[maxn],cur[maxn];
bool bfs(){
    queue<int> q;
    memset(dep,-1,sizeof(dep));
    dep[s]=0; q.push(s);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dep[v]==-1&&e[i].w>eps){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}
double dfs(int u,double flow){
    if(u==t) return flow;
    double used=0;
    for(int i=cur[u];i;i=e[i].next){
        cur[u]=i; 
        int v=e[i].to;
        if(dep[v]==dep[u]+1&&e[i].w>eps){
            double rlow=dfs(v,min(flow-used,e[i].w));
            if(rlow>eps){
                e[i].w-=rlow; e[i^1].w+=rlow;
                used+=rlow;
                if(fabs(flow-used)<eps) break;
            }
        }
    }
    return used;
}
double dinic(){
    double ans=0;
    while(bfs()){
        memcpy(cur,head,sizeof(cur));
        ans+=dfs(s,inf);
    }
    return ans;
}
void reset(double x){
    memset(head,0,sizeof(head)); tot=1;
    for(int i=1;i<=m;i++){
        double cap=min(x,w[i]);
        add(u[i],v[i],cap),add(v[i],u[i],0);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>p; s=1,t=n;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        add(u[i],v[i],w[i]); add(v[i],u[i],0);
        maxm=max(maxm,w[i]);
    }
    double l=0,r=maxm,ans=r;
    double f=dinic();
    while(r-l>eps){
        double mid=(l+r)/2;
        reset(mid);
        if(dinic()>=f-eps){
            ans=mid;
            r=mid;
        }
        else l=mid;

    }
    printf("%.0lf\n%.4lf",f,ans*p);
    return 0;
}

总结

此题唯一难点在于二分，甚至说建图都是模版式建图。

建议降蓝。

觉得自己二分不好的可以做完此题后，再做做 这道题。