UVA-Live 7740 Coding Contest （费用流）

UVA-Live 7740 Coding Contest （费用流）

之所以不写HDU 5988是因为杭电的土豆评测机就是给我T，疯狂T，最后发现别人的题解有写UVA-Live的，那我就去试试，结果常数最糟糕的STL版本我都过了。。。992ms，还是很悬很悬。不管了，现场赛的评测机都很厉害很厉害的，不想在意这种常数细节了，反正都临近退役了，多刷点别的题也比死磕这题的常数好啊。

题意

中国石油大学举办ICPC青岛站比赛，比赛的时候体育馆被划分为了N个区域，送午餐的时候发现路不好走，中间可能会绊到线，于是志愿者只把面包放在部分区域内，让选手自己过来拿。此时第i个区域内有$s_i$si​个人，$b_i$bi​包午餐。每条连接u区域到v区域的单向路上最多能走c个人，再多一点这条路上的线会被踩烂，第一个通过这个路的人不会踩坏线，而后面通过这条路的人有p(1>p>0)可能会被线绊到，被绊到就会把整个网络搞瘫痪让选手去知乎骂主办方（雾），求让所有的选手都吃到午饭而不使网络崩溃的概率。

思路

这年的青岛怎么这么多概率题啊。C题概率推公式，D题概率DP，G题就是概率加网络流，真的烦，恨不得回去重修概率论。

首先思路还是比较明显的就是费用流，但是我模拟赛的时候以下几点根本没有考虑到，导致敲了两个小时愣是没写出来，最后还是得看大佬的博客，还是太菜了。

1. 概率乘法的转加法处理 很显然踩坏线的概率就是该边的费用。但是我们的最短路算法们松弛的操作都是用加法，从来没有用乘法的，因为之前写过类似的题（hdu 6290 奢侈的旅行），所以很快我就想到用log来解决乘法转加法的问题。但是这题还要考虑把log转换回来，我并没有用过exp()函数，这就触及到我的知识盲区了，差点开始研究double快速幂。
2. 源点和汇点 马后炮想到的。我们可以先让各个区域的人把自己区域的面包吃了，然后有多余的人的，那就当是从源点来的，有面包多的，就说明还有人可以通过该点去汇点。本来我打模拟赛的时候打算暴力枚举源点、汇点来跑，还好我样例都没过。大佬们呢，就是把源点和所有的有人的区域连，把所有有面包的区域和汇点连，简单粗暴，但我不知道我为什么比这种建图方式还慢了10ms。所有和源点、汇点连的边费用都是0 。
3. 第一次走不会碰掉线 这点好办，直接把原来的边拆出个重边就行，容量为1，费用为0 。
4. 费用为负的处理 我们已经把概率转成log来实现加法了，但是，问题来了，这个时候因为${0 &lt; p_i &lt; 1}$0<pi​<1，所以log完以后是个负数。上面已经把包含源点和汇点的边还有第一次走的边都设为费用为0了，这样布星，因为此时我们跑的最短路依然是费用越小越好，那么我们应该让这些费用为0的点变成费用负无穷，那转换回来log又涉及到精度问题了。取反的话不是要求最大费用流？最大费用的不是一般也是取反来做么。。。所以我们可以转换成求踩不坏的概率（1-p），再取反求最小费用流。

其他注意事项还有eps的设置（不加的话double的精度比较高，只求两位小数的话多算几轮没有意义，会T）、double费用不能初始化dis数组全都为0x3f3f3f3f了（这里用了常用大质数1e9+7，好多大佬都喜欢这个数字）、不要忘了网络流所有的边都有反向边。这次是我第一次写链式前向星，然后发现其实它本质思想和刘汝佳的链表是一毛一样的。

代码

#include <bits/stdc++.h>

#define  INF 0x3f3f3f3f
#define  DBL 1000000007
using namespace std;
struct edge
{
    int from;
    int to;
    int flow;
    int cap;
    double cost;
    int nxter;//链式前向星指向下一条边
    edge(int f,int t,int c,double co,int n):from(f),to(t),cap(c),cost(co),nxter(n){
        flow=0;
    }
};
vector<edge> edges;//存所有边
static const double eps = 1e-4;
int egs[205];
void addedge(int u,int v,int c,double p)
{
    edges.emplace_back(u, v, c, -log(1 - p), egs[u]);
    egs[u] = edges.size() - 1;
    edges.emplace_back(v, u, 0, log(1 - p), egs[v]);//网络流里所有的边都要加反向边
    egs[v] = edges.size() - 1;
}
double dis[205];
bool vis[205];
int pre[205];
int visitor[205];
int flower[205];
int n,m;
int bellmanford(int s,int t)
{
    for(int i=0;i<=n+1;i++)
    {
        dis[i]=DBL;
    }
    memset(vis,0,sizeof vis);
    memset(pre,-1,sizeof pre);
    memset(visitor,0,sizeof visitor);
    memset(flower,0,sizeof flower);
    dis[s]=0;
    flower[s]=INF;
    deque<int> qq;
    qq.push_back(s);
    vis[s]=true;
    while(!qq.empty())
    {
        int now=qq.front();
        qq.pop_front();
        visitor[now]++;
        if(visitor[now]>n)
        {
            return -1;
        }
        for(int i= egs[now];i!=-1;i=edges[i].nxter)
        {
            edge nxt = edges[i];
            int tempflow = min(flower[now],nxt.cap-nxt.flow);
            double lener=nxt.cost;
            if(nxt.cap-nxt.flow>0 && dis[nxt.to] > dis[now] + lener + eps )
            {

                dis[nxt.to]=dis[now]+lener;
                //cout<<now<<" "<<nxt.to<<" "<<dis[nxt.to]<<endl;
                pre[nxt.to]=i;
                flower[nxt.to]=tempflow;
                if(!vis[nxt.to])
                {
                    if(!qq.empty() && dis[nxt.to]<dis[qq.front()])
                    {
                        qq.push_front(nxt.to);
                    } else{
                        qq.push_back(nxt.to);
                    }
                    vis[nxt.to]=true;
                }
            }
        }
        vis[now]=false;
    }
    if(dis[t]<DBL)
    {
        return flower[t];
    }
    else
    {
        return -1;
    }

}
double MFMC(int ss,int tt) {
    int maxflow = 0;
    double mincost = 0;
    int nowflow = 0;
    while (nowflow = bellmanford(ss, tt) > 0) {
        maxflow += nowflow;
        mincost += dis[tt] * nowflow;
        int now = tt;
        while (now!=ss) {
            edges[pre[now]].flow += nowflow;
            edges[pre[now] ^ 1].flow -= nowflow;//回溯加流量
            now = edges[pre[now]].from;
        }
    }
    return 1-exp(-mincost);//把费用转换回概率
}
int main() {
    int t;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--) {
        cin >> n >> m;
        memset(egs,-1,sizeof egs);
        edges.clear();
        for (int i = 1; i <= n; i++) {
            int s,b;
            cin >> s >> b;
            if(s>b)
            {
                addedge(0,i,s-b,0);//人都是从源点来的
            }
            if(b>s)
            {
                addedge(i,n+1,b-s,0);//人吃完面包都要到汇点去的
            }

        }
        for (int i = 0; i < m; i++) {
            int u, v, c;
            double f;
            cin >> u >> v >> c;
            cin >> f;
            addedge(u,v,c-1,f);
            addedge(u,v,1,0);
        }
        cout<<fixed<<setprecision(2)<<MFMC(0,n+1)<<endl;
    }
    return 0;
}

参考了以下博主的文章，在此表示感谢：

https://www.cnblogs.com/Q1143316492/p/9751794.html

https://blog.csdn.net/FTQOOO/article/details/53715117

https://www.cnblogs.com/xiuwenli/p/9748187.html

http://c.biancheng.net/cpp/html/184.html