SDOI2013 费用流

wjh15101051's space

卧薪尝胆，厚积薄发。

SDOI2013 费用流

Date: Wed Mar 20 16:53:21 CST 2019

In Category: NoCategory

Description：

给一个网络流图， $A$ 给出一个最大流， $B$ 再每条边上分配花费，要求所有边花费之和为 $P$ ， $A$ 希望总费用尽量小， $B$ 希望尽量大，求这个费用。

$1\leqslant n\leqslant 10^2,1\leqslant m\leqslant 10^3$

Solution：

首先对于 $B$ 最值的显然是把所有费用都放到最大流量的边上，于是我们希望最大流最小，二分 $+dinic$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,p;

#define MAXN 110

#define MAXM 1010

struct edges

{

	int u,v,w;

}es[MAXM];

struct edge

{

    int to,nxt;

	double f;

}e[MAXM * 2];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,double f)

{

    e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

    e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

    return;

}

#define INF 0x3f3f3f3f

int s,t;

int ch[MAXN];

bool BFS()

{

    memset(ch,-1,sizeof(ch));ch[s] = 0;

    queue<int> q;q.push(s);

    while(!q.empty())

    {

        int k = q.front();q.pop();

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(ch[e[i].to] == -1 && e[i].f > 0)

            {

                ch[e[i].to] = ch[k] + 1;

                q.push(e[i].to);

            }

        }

    }

    return (ch[t] != -1);

}

double flow(int k,double f)

{

    if(k == t)return f;

    double r = 0;

    for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

    {

        if(ch[e[i].to] == ch[k] + 1 && e[i].f > 0)

        {

            double l = flow(e[i].to,min(e[i].f,f - r));

            e[i].f -= l;r += l;e[i ^ 1].f += l;

        }

    }

    if(r == 0)ch[k] = -1;

    return r;

}

#define INF 0x3f3f3f3f

double dinic()

{

    double ans = 0,r;

    while(BFS())while(r = flow(s,1000000000))ans += r;//cout << ans << endl;

    return ans;

}

void build(double val)

{

    memset(lin,-1,sizeof(lin));

    edgenum = 0;

	for(int i = 1;i <= m;++i)

	{

		add(es[i].u,es[i].v,min(1.0 * es[i].w,val));

	}

	return;

}

int main()

{

    scanf("%d%d%d",&n,&m,&p);

    for(int i = 1;i <= m;++i)

    {

		scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].w);

	}

	s = 1;t = n;

	build(1000000000);

	int maxflow = dinic();

	double l = 0,r = 1000000000,mid;

	while(r - l > 1e-8)

	{

		mid = (l + r) / 2;

		build(mid);

		if(dinic() == maxflow)r = mid;

		else l = mid;

	}

	cout << maxflow << endl;

    printf("%.10lf\n",l * p);

    return 0;

}

In tag: 数学-博弈论-纳什均衡图论-dinic

wjh15101051