文章标题 UVALive 7740 ： Coding Contest （费用流+精度）

Coding Contest

松弛的时候注意价格我 eps 精度，通过这道题也练了下dijkstra的费用流。
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;

const double eps=1e-8;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn=1e5+10;
typedef pair<double,int>pii;

struct Edge{
    int to,cap;
    double cost;
    int rev;
};
int n,m;
struct MFMC{
    int n;//定点数 
    vector<Edge>G[maxn];//图的表示 
    double dis[maxn];//最短距离 
    double h[maxn];//定点的势 
    int prevv[maxn],preve[maxn];//最短路中的前驱节点和对应的边 

    void init(int n_){//初始化 
        n=n_;
        for (int i=0;i<n_;i++)G[i].clear();
    }

    //想图中增加一条u->v容量为cap,费用为cost 的边 
    void addedge(int u,int v,int cap,double cost){
        G[u].push_back(Edge{v,cap,cost,(int)G[v].size()});
        G[v].push_back(Edge{u,0,-cost,(int)G[u].size()-1});
    }
    //求解s->t容量为flow 的最小费用
    //如果不能增广则返回-1（即s->t没有flow的流量） 
    double min_cost_flow(int s,int t,int flow){
        double res=0.0;
        for (int i=0;i<n;i++)h[i]=0.0;
        while (flow>0){
            //dijkstra求最短路 
            priority_queue<pii, vector<pii>, greater<pii> >que;
            for (int i=0;i<n;i++)dis[i]=inf;
            dis[s]=0.0;
            que.push(make_pair(0,s));
            while (!que.empty()){
                pii p=que.top();que.pop();
                int v=p.second;
                if (dis[v]<p.first)continue;
                for (int i=0;i<G[v].size();i++){
                    Edge &e=G[v][i];
                    if (e.cap>0&&dis[e.to]>dis[v]+h[v]+e.cost-h[e.to]+eps){
                        dis[e.to]=dis[v]+e.cost+h[v]-h[e.to];
                        prevv[e.to]=v;
                        preve[e.to]=i;
                        que.push(make_pair(dis[e.to],e.to));
                    }
                }
            }
            if (dis[t]==inf){
                return -1;
            }
            for (int v=t;v!=s;v=prevv[v])h[v]+=dis[v];
            int d=flow;
            for (int v=t;v!=s;v=prevv[v]){
                d=min(d,G[prevv[v]][preve[v]].cap); 
            } 
            flow-=d;
            res+=d*h[t]; 
            for (int v=t;v!=s;v=prevv[v]){
                Edge &e=G[prevv[v]][preve[v]];
                e.cap-=d;
                G[v][e.rev].cap+=d;
            }
        }
        return res;
    }
}mfmc;  

int main()
{
    int T;
    scanf ("%d",&T);
    while (T--){
        scanf ("%d%d", &n, &m);
        mfmc.init(n+2) ;
        int s=0, t=n+1;
        int a,b;
        int f=0;
        for (int i=1;i<=n;i++){
            scanf ("%d%d",&a,&b);
            if (a>b){
                mfmc.addedge(s,i,a-b,0);
                f+=a-b;
            }else if (b>a){
                mfmc.addedge(i,t,b-a,0);
            }
        }
        int u,v,c;
        double p;
        for (int i=1;i<=m;i++){
            scanf ("%d%d%d%lf",&u,&v,&c,&p);
            p=-(log(1.0-p));
            if(c == 0) continue;
            else if(c == 1) mfmc.addedge(u,v,1,0);
            else {
                mfmc.addedge(u,v,c-1,p);
                mfmc.addedge(u,v,1,0);
            }
        }
        double ans = mfmc.min_cost_flow(s, t, f);
        //printf ("flow=%d\n",ret);
        //printf ("ans=%f\n",ans);
        //printf ("exp=%f\n",exp(-ans));
        ans = 1.0-exp(-ans);
        printf ("%.2f\n",ans);
    }
    return 0;
}
/*
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
*/