题解 P3305 【[SDOI2013]费用流】

硫代硫酸钠 · 2018-03-08 11:11:45 · 题解

首先不要被标题迷惑哦,这个题跟费用流关系不大.

然后就是重边,个人认为重边不应去除,理由如下:

显然根据本题的模型,在答案的最大流方案中流量最高的边收费p即可.

这样就导致简单合并边可能不对. 虽然这种做法能骗到80

正解:

在答案的最大流方案中流量最高的边收费p,要求答案最大流方案流量最多的边实际流量最小.考虑二分流量上界,对于上界判断是否能形成最大流.

本蒟蒻第一道实数二分...

#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define size 500010
#define debug(x) cerr<<#x<<"="<<x
#define gc getchar()
#define tp to[p]
#define inf 1e9+9
#define eps 1e-5
#define ll long long
#define db double
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#define drep(i,n,s) for (register int i=n;i>=s;i--)
#define il inline
using namespace std;

il ll r()
{
    char c; ll x,f=1;
    for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
    for (c=gc;isdigit(c);c=gc) x=(x<<1)+(x<<3)+c-'0';
    return f*x;
}

int head[size],to[size],nxt[size],num=1,S,T,sta[size],q[size],n,m,cur[size];
db mx,len[size],lim=1e15,lenn[size],p;

void add(int x,int y,db z)
{
    num++; to[num]=y;lenn[num]=z; nxt[num]=head[x];head[x]=num;
}

void create(int x,int y,db z) { add(x,y,z); add(y,x,0); }

bool bfs()
{
    int f=0,r=0;
    memset(sta,-1,sizeof(sta));
    q[++r]=S,sta[S]=0;
    while (f<r)
    {
        int x=q[++f]; 
        for (int p=head[x];p;p=nxt[p])
            if (len[p]>0&&sta[tp]==-1) sta[tp]=sta[x]+1,q[++r]=tp;      
    }
    if (~sta[T]) return 1; return 0; 
}

db dfs(int x,db flow)
{
    if (x==T) return flow;
    db now=0,used=0;
    for (int &p=cur[x];p;p=nxt[p])
        if (len[p]>0&&sta[tp]==sta[x]+1)
        {
            now=dfs(tp,min(len[p],flow-used)); used+=now;
            len[p]-=now; len[p^1]+=now; if (used==flow) break;
        }
    return used; 
}

void init()
{
    rep(i,1,num) len[i]=min(lenn[i],lim); 
}

db dinic()
{
    db ans=0;
    while (bfs())
    {
        rep(i,1,n) cur[i]=head[i];
        ans+=dfs(S,1e9+7); 
    }
    return ans;
}

int main()
{
    n=r(),m=r(); S=1,T=n; cin>>p;
    rep(i,1,m) 
    {
        int x,y; db z;
        scanf("%d%d%lf",&x,&y,&z); create(x,y,z);
    }
    init(); 
    db mf=dinic();printf("%.4lf\n",mf);
    db lb=0,rb=1e9,ans=0;
    while (rb-lb>0.00001) 
    {
        db mid=(lb+rb)/2;
        lim=mid; init();
        db nowflow=dinic();
        if (fabs(nowflow-mf)<0.00001) rb=mid,ans=mid;
        else lb=mid; 
    }
    lim=ans; init(); int t=dinic();  db mx=0;
    for (int i=1;i<=num;i+=2)  mx=max(mx,len[i]); printf("%.5lf",mx*p); 
    return 0;
}