BruceJay's Blog

BZOJ3130 费用流

| Comments

To start with

二分+网络流。

Problem

Solution

对于费用分配,将所有费用分给流量最大的边就是了。
所以二分,检验一下是否与原图最大流相等就可以了。
二分一定要实数二分,此处给个例子(别的地方蒯的):
(起点,终点,容量)
(1,3,3)
(1,2,3)
(2,3,3)
(3,4,2)
(3,5,2)
(3,6,1)
(4,7,2)
(5,7,2)
(6,7,2)
答案是2.5

Code

#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
const int M = 2010;
const double INF = 5e4;
const double eps = 1e-5;
struct Edge{int u,v;double w,cap,flow;int nxt;}e[M];
int head[N]; int cur[N]; int h[N];
queue<int> q;
int n,m,cnt=1,maxflow; double k,ans;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v,double cap)
{
    e[++cnt]=(Edge){u,v,cap,cap,0,head[u]}; head[u]=cnt;
    e[++cnt]=(Edge){v,u,0,0,0,head[v]}; head[v]=cnt;
}

bool Bfs()
{
    memset(h,-1,sizeof(h));
    h[1]=0; q.push(1);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].nxt)
            if(h[e[i].v]==-1 && e[i].cap>e[i].flow){
                h[e[i].v]=h[u]+1; q.push(e[i].v);
            }
    }
    return h[n]!=-1;
}

double Dfs(int u,double now)
{
    double flow=0;
    if(u==n || now<=eps) return now;
    for(int& i=cur[u];i;i=e[i].nxt)
        if(h[e[i].v]==h[u]+1){
            double f=Dfs(e[i].v,min(now,e[i].cap-e[i].flow));
            e[i].flow+=f; e[i^1].flow-=f;
            flow+=f; now-=f; if(now<=eps) break;
        }
    return flow;
}

double Dinic()
{
    double flow=0;
    while(Bfs()){
        memcpy(cur,head,sizeof(head));
        flow+=Dfs(1,INF);
    }
    return flow;
}

bool Check(double mid)
{
    for(int i=2;i<=cnt;i++){
        e[i].cap=min(mid,e[i].w); e[i].flow=0;
    }
    return fabs(Dinic()-maxflow)<=eps;
}

int main()
{
    int u,v,c;
    freopen("3130.in","r",stdin);
    freopen("3130.out","w",stdout);
    n=read(); m=read(); k=read();
    for(int i=1;i<=m;i++){
        u=read(); v=read(); c=read();
        Addedge(u,v,c);
    }
    maxflow=Dinic();
    double l=0,r=maxflow,mid;
    while(r-l>eps){
        mid=(l+r)/2;
        if(Check(mid)) ans=r=mid;
        else l=mid;
    }
    printf("%d\n%.4lf",maxflow,ans*k);
    return 0;
}

Last but not least

想不到啊,怎么办!!!

Comments

comments powered by Disqus