Bakser's Blog

我是逗比。

bzoj3130 [Sdoi2013][费用流] 二分+最大流

| Comments

这题跟费用流有什么关系吗?

可以证明Bob每次的决策一定是将所有单价加在了流量最大的边上

证明
设从p中分出了k的单价加给了一条流量非最大的边(设流量为flow,设流量最大边流量为maxflow
则这种决策更优当且仅当
    (p-k)*maxflow+k*flow>p*maxflow
  移项得k*flow>k*maxflow
  flow>maxflow,与maxflow是流量最大的边矛盾。
  (好吧这么水我还要证明真是秀智商)

然后Alice就是要在满足最大流的前提下使流量最大的边流量最小。二分这个上界即可。

bzoj3130
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 110
#define M 2400
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
typedef double LD;
const LD INF(1e40),eps(1e-5);
inline int cmp(LD x)
{
    if(x>eps)return 1;
    if(x<-eps)return -1;
    return 0;
}
struct hh
{
    int next,u,v;
    LD cap,flow;
}edges[M];
int n,m,s,t,point[N],cur[N],d[N],p[N],gap[N],en(-1);
LD q;
inline void addedge(int u,int v,LD cap)
{
    edges[++en].next=point[u];point[u]=en;edges[en].u=u;edges[en].v=v;
    edges[en].cap=cap;edges[en].flow=cap;
}
inline LD augment(LD lim)
{
    LD flow(INF);
    for(int x(t);x!=s;x=edges[p[x]].u)
        flow=MIN(flow,edges[p[x]].cap);
    for(int x(t);x!=s;x=edges[p[x]].u)
        edges[p[x]].cap-=flow,edges[p[x]^1].cap+=flow;
    return flow;
}
inline void bfs()
{
    static queue<int> q;
    memset(d,0xff,sizeof(d));
    gap[d[t]=0]++;q.push(t);
    while(!q.empty())
    {
        int u(q.front());q.pop();
        for(int i(point[u]);i!=-1;i=edges[i].next)
            if(cmp(edges[i^1].cap)>0&&d[edges[i^1].u]==-1)
            {
                gap[d[edges[i^1].u]=d[u]+1]++;
                q.push(edges[i^1].u);
            }
    }
}
inline LD isap(LD lim)
{
    int x(s);LD res(0);
    memcpy(cur,point,(n+5)*sizeof(int));
    bfs();
    while(d[s]<n)
    {
        if(x==t)
            res+=augment(lim),x=s;
        bool flag(0);
        for(int i(cur[x]);i!=-1;i=edges[i].next)
            if(cmp(edges[i].cap)>0&&d[x]-1==d[edges[i].v])
                {
                    flag=1;
                    cur[x]=i;
                    x=edges[i].v;
                    p[x]=i;
                    break;
                }
        if(!flag)
        {
            int delta(n);
            if(!--gap[d[x]])break;
            for(int i(point[x]);i!=-1;i=edges[i].next)
                if(cmp(edges[i].cap)>0&&d[edges[i].v]<delta)
                    {
                        delta=d[edges[i].v];
                        cur[x]=i;
                    }
            gap[d[x]=delta+1]++;
            if(x!=s)x=edges[p[x]].u;
        }
    }
    return res;
}
inline LD MaxFlow(LD lim)
{
    for(int i(0);i<=en;i++)
        edges[i].cap=MIN(edges[i].flow,lim);
    return isap(lim);
}
int main()
{
    scanf("%d%d%lf",&n,&m,&q);
    memset(point,0xff,sizeof(point));
    s=1;t=n;LD l(0),r(0);
    for(int i(0);i<m;i++)
    {
        int u,v;LD w;
        scanf("%d%d%lf",&u,&v,&w);
        r=MAX(r,w);
        addedge(u,v,w);
        addedge(v,u,0);
    }
    LD maxflow(isap(INF)),ans(1);
    while(r-l>eps)
    {
        LD mid((l+r)/2.0);
        if(MaxFlow(mid)==maxflow)r=mid,ans=mid;
        else l=mid;
    }
    ans*=q;
    printf("%.0lf\n%.4lf",maxflow,ans);
    return 0;
}

Comments

comments powered by Disqus