索鸟网

  1. 首页
  2. HDU 5988 Coding Contest (最小费用流)

HDU 5988 Coding Contest (最小费用流)


Description

A coding contest will be held in this university, in a huge playground. The whole playground would be divided into N blocks, and there would be M directed paths linking these blocks. The i-th path goes from the ui-th block to the vi-th block. Your task is to solve the lunch issue. According to the arrangement, there are si competitors in the i-th block. Limited to the size of table, bi bags of lunch including breads, sausages and milk would be put in the i-th block. As a result, some competitors need to move to another block to access lunch. However, the playground is temporary, as a result there would be so many wires on the path.

For the i-th path, the wires have been stabilized at first and the first competitor who walker through it would not break the wires. Since then, however, when a person go through the i - th path, there is a chance of pi to touch the wires and affect the whole networks. Moreover, to protect these wires, no more than ci competitors are allowed to walk through the i-th path.

Now you need to find a way for all competitors to get their lunch, and minimize the possibility of network crashing.

 

Input

The first line of input contains an integer t which is the number of test cases. Then t test cases follow.

For each test case, the first line consists of two integers N (N ≤ 100) and M (M ≤ 5000). Each of the next N lines contains two integers si and bi (si , bi ≤ 200).

Each of the next M lines contains three integers ui , vi and ci(ci ≤ 100) and a float-point number pi(0 < pi < 1).

It is guaranteed that there is at least one way to let every competitor has lunch.

 

Output

For each turn of each case, output the minimum possibility that the networks would break down. Round it to 2 digits.

 

Sample Input

1
4 4
2 0
0 3
3 0
0 3
1 2 5 0.5
3 2 5 0.5
1 4 5 0.5
3 4 5 0.5

 

Sample Output

0.50

 

题意

n 个区域,每个区域都有一些人和食物,区域之间存在 m 条有向路径,每条路都有一个人数上限。路径之间铺了电线,每当有人通过时都会有 pi 的概率碰到它,但是第一个通过的人一定不会碰到,求所有人都获取到食物而碰到电线的最小概率。

 

思路

最小费用流的基础题。

首先我们可以让某个区域的人得到当前他所在区域的某个食物,然后原图转化为每一个点存在一些人或者存在一些食物,要求碰到电线的最小概率也就是不碰到电线的最大概率。

假设碰到某条电线的概率为 p ,那不碰到它的概率即为 1p ,而我们在费用流中的费用是相加得到的,怎么才能转化为那种形式呢?

我们知道 log2(ab)=log2a+log2b ,于是对 1p 取对数,边的费用就变成了 log2(1p) (负边权求最大值相当于正边权求最小值),边容量为 cap1 (因为有 cap1 个人通过这条路径有几率碰到电线),对于第一个人所对应的边,费用为 0 ,容量为 1

随后从源点向每一个人所在的节点连有向边,每一个食物所在的节点向汇点连有向边,找最小费用即可。


PS: 这道题目卡常好严重,貌似 1000ms 的题目 998ms 过的。

So ,如果 TLE 可以考虑再提交一下。

 

AC 代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 105;
const int maxm = 21000;
const int INF = 2e9;
const double eps = 1e-8;

struct edge
{
    int to;     //边终点
    int next;   //下一个兄弟位置
    int cap;    //容量
    int flow;   //流量
    double cost;   //费用
} edge[maxm];

int head[maxn],tol;
int pre[maxn];
double dis[maxn];
int N;  //节点总个数
bool vis[maxn];

int person[maxn],thing[maxn];

void init(int n)
{
    N=n;
    tol=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int cap,double cost)  //同时增加原边与反向边
{
    edge[tol].to=v;
    edge[tol].cap=cap;
    edge[tol].cost=cost;
    edge[tol].flow=0;
    edge[tol].next=head[u];
    head[u]=tol++;
    edge[tol].to=u;
    edge[tol].cap=0;
    edge[tol].cost=-cost;
    edge[tol].flow=0;
    edge[tol].next=head[v];
    head[v]=tol++;
}

/*
 * SPFA 算法判断是否存在s到t的通路
 */
bool spfa(int s,int t)
{
    queue<int>q;
    for(int i=0; i<N; i++)
    {
        dis[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    dis[s]=0;
    vis[s]=true;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u]; i!=-1; i=edge[i].next)   //遍历所有与u临接的点
        {
            int v=edge[i].to;
            if(edge[i].cap>edge[i].flow&&dis[v]-dis[u]-edge[i].cost>eps)    //如果可以松弛该点
            {
                dis[v]=dis[u]+edge[i].cost;
                pre[v]=i;
                if(!vis[v]) //如果该点不在队列中,入队
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    return (pre[t]!=-1);    //返回是否s到t是否有路径
}

/*
 * int s 起点
 * int t 终点
 */
int minCostMaxFlow(int s,int t,double &cost)
{
    int flow=0;
    while(spfa(s,t))
    {
        int minn=INF;   //当前路径可增广值
        for(int i=pre[t]; i!=-1; i=pre[edge[i^1].to])   //因为建图时每增加一条边会同时加入它的反向边,因此i^1为找出与i刚好相反的部分
        {
            if(minn>edge[i].cap-edge[i].flow)
                minn=edge[i].cap-edge[i].flow;
        }
        for(int i=pre[t]; i!=-1; i=pre[edge[i^1].to])   //修改图,计算花费
        {
            edge[i].flow+=minn;
            edge[i^1].flow-=minn;
            cost+=edge[i].cost*minn;
        }
        flow+=minn;
    }
    return flow;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n=0,m=0;
        scanf("%d%d",&n,&m);
        init(n+2);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",person+i,thing+i);
            person[i]-=thing[i];
        }
        for(int i=0; i<m; i++)
        {
            int u=0,v=0,cap=0;
            double p;
            scanf("%d%d%d%lf",&u,&v,&cap,&p);
            p = -log2(1.0-p);
            if(cap>1)
                addedge(u,v,cap-1,p);
            if(cap>0)
                addedge(u,v,1,0);
        }
        for(int i=1; i<=n; i++)
        {
            if(person[i]>0)
                addedge(0,i,person[i],0);
            else
                addedge(i,n+1,-person[i],0);
        }
        double cost = 0;
        minCostMaxFlow(0,n+1,cost);
        printf("%.2f\n",1.0-pow(2,-cost));
    }
    return 0;
}

来源地址:http://blog.csdn.net/qq_28954601/article/details/78232734 版权归作者所有!

相关教程

  • 1227 方格取数 2 费用流

    题目链接 要点,每个点之间可以连两条边,这样可以解决很多问题,该题中的数据被取出,则可以连一条有权重的边和若干条无权重的边. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 10000; const int MAXM
  • [2009哈尔滨]J - FM UVALive - 4772 最小费用最大流

    题目链接 S向每个人连一条容量为1 费用为0 的边 , 每个人向职位连容量为1 费用为-point的边,每个职位根据模式向T连费用为0的边. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 10000; const int MAXM = 100000;
  • BZOJ 2597: [Wc2007]剪刀石头布 费用流

    题意 给你一个竞赛图,有的边还没被定向。要你求一种定向方案,使得简单三元环的数量最多。 n<=100 分析 果然还是我太菜。。。 注意到任选三个点,若不能组成三元环,则必然有一个点的出边数量位2,所以简单三元环的数量即为C3n−∑ni=1C2degree[x]C_n^3-\sum_{i=1}^nC_{degree[x]}^2 考虑转化成费用流模型: 把每条边看做一个点。
  • UVa11613 - Acme Corporation(不定流量的费用流)

    题目链接 简介: 生产一种产品,每个月有最大销量,销售单价,最大产量,生产成本,储存期限,储存也需要一定花费,求M个月中的最大利润 分析: 把每一个月拆成两个点 x1,x2 源点向x1连边,流量是每个月的最大产量,费用是生产成本 x2向汇点连边,流量是每个月的最大销量,费用是销售价格的相反数 x1向x2连边,流量为INF,费用是0 x1向(x+1)
  • [费用流]LOJ#6079. 「2017 山东一轮集训 Day7」养猫

    nn个时刻,猫在每个时刻要么是吃东西,要么是睡觉。在第eie_i​,假如是去睡觉,那么能获得的愉悦值为kk的作息区间,即所有的时刻区间ms\text{ms} 的时刻用来睡觉,nn个时刻,使得猫在能健康成长的前提下,获得尽量多的愉悦值。
  • 网络流(多样的建模)

    yhzq的总结是非常好的: 网络流总结 然而博主也不是一个只会复制链接的人,还是要有一点自己的感悟的 网络流问题最重要的就是建模和模型转换,下面就给出一些 经典模型 一、最大流 多源多汇问题 源有多个,汇也有多个,流可以从任意源流出,最终可以流向任意汇, 总流量等于所有源流出的总流量(所有汇流入的总流量) 解:加一个超级源点S,和超级汇点
  • Coding Standard

    Coding Standards 转载自掘金 作者:Sivan 简介:前端开发的老新人,原生JavaScript的爱好者,致力做一名专业的开发者 javascript 代码规范 代码规范我们应该遵循古老的原则:“能做并不意味着应该做”。 全局命名空间污染 总是将代码包裹在一个立即的函数表达式里面,形成一个独立的模块。 不推荐 var x =
  • 网络流建模汇总(转自Edelweiss)

    最大流 《POJ 1149    PIGS》  【题目大意】 有 M 个猪圈,每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依 次来了 N  个顾客,每个顾客分别会打开指定的几个猪圈,从中买若干头猪。每个顾客分别都有他能够买的数量的上限。每个顾客走后,他打开的那些猪圈中的 猪,都可以被任意地调换到其它开着的猪圈