Coding Contest(费用流变形题，double)

Coding Contest

http://acm.hdu.edu.cn/showproblem.php?pid=5988

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 5337 Accepted Submission(s): 1256

Problem 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

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

Output

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

Sample Input

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

Source

2016ACM/ICPC亚洲区青岛站-重现赛（感谢中国石油大学）

求网络被破坏的最小可能性，因为是乘法，所以要用取对数的方法把它改成加法。

因为概率是小于1的，所以取对数完是负数，需要用 - 把它转为正数。

但是转为正数后，原来的最小值就会变为最大值，所以用p=-log2(1-p)，转为求不被破坏的最大可能行，跑费用流

因为是浮点型，所以在松弛的时候要加上eps。

最后，要用for去代替memset,不然可能会t...

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<cstdio>
  7 using namespace std;
  8 
  9 const double eps=1e-9;
 10 const int INF=0x3f3f3f3f;
 11 const int N=500005;
 12 const int M=500005;
 13 int top;
 14 double dist[N];
 15 int pre[N];
 16 bool vis[N];
 17 int c[N];
 18 int maxflow;
 19 
 20 struct Vertex{
 21     int first;
 22 }V[N];
 23 struct Edge{
 24     int v,next;
 25     int cap,flow;
 26     double cost;
 27 }E[M];
 28 
 29 void init(int num){
 30    // memset(V,-1,sizeof(V));
 31     for(int i=0;i<num;i++){
 32         V[i].first=-1;
 33     }
 34     top=0;
 35     maxflow=0;
 36 }
 37 
 38 void add_edge(int u,int v,int c,double cost){
 39     E[top].v=v;
 40     E[top].cap=c;
 41     E[top].flow=0;
 42     E[top].cost=cost;
 43     E[top].next=V[u].first;
 44     V[u].first=top++;
 45 }
 46 
 47 void add(int u,int v,int c,double cost){
 48     add_edge(u,v,c,cost);
 49     add_edge(v,u,0,-cost);
 50 }
 51 
 52 bool SPFA(int s,int t,int n){
 53     int i,u,v;
 54     queue<int>qu;
 55    // memset(vis,false,sizeof(vis));
 56   //  memset(c,0,sizeof(c));
 57    // memset(pre,-1,sizeof(pre));
 58     for(i=0;i<=n+2;i++){
 59         dist[i]=INF;
 60         vis[i]=false;
 61         c[i]=0;
 62         pre[i]=-1;
 63     }
 64   //  memset(dist,INF,sizeof(dist));
 65     vis[s]=true;
 66     c[s]++;
 67     dist[s]=0;
 68     qu.push(s);
 69     while(!qu.empty()){
 70         u=qu.front();
 71         qu.pop();
 72         vis[u]=false;
 73         for(i=V[u].first;~i;i=E[i].next){
 74             v=E[i].v;
 75             if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost+eps){
 76                 dist[v]=dist[u]+E[i].cost;
 77                 pre[v]=i;
 78                 if(!vis[v]){
 79                     c[v]++;
 80                     qu.push(v);
 81                     vis[v]=true;
 82                     if(c[v]>n){
 83                         return false;
 84                     }
 85                 }
 86             }
 87         }
 88     }
 89     if(dist[t]==INF){
 90         return false;
 91     }
 92     return true;
 93 }
 94 
 95 double MCMF(int s,int t,int n){
 96     int d,i;
 97     double mincost=0;
 98     while(SPFA(s,t,n)){
 99         d=INF;
100         for(i=pre[t];~i;i=pre[E[i^1].v]){
101             d=min(d,E[i].cap-E[i].flow);
102         }
103         maxflow+=d;
104         for(i=pre[t];~i;i=pre[E[i^1].v]){
105             E[i].flow+=d;
106             E[i^1].flow-=d;
107         }
108         mincost+=dist[t]*d;
109     }
110     return mincost;
111 }
112 
113 int main(){
114     int n,m;
115     int T;
116     scanf("%d",&T);
117     while(T--){
118         scanf("%d %d",&n,&m);
119         init(n+3);
120         int a,b,c;
121         double p;
122         int s=0,t=n+1;
123         for(int i=1;i<=n;i++){
124             scanf("%d %d",&a,&b);
125             if(a>b){
126                 add(s,i,a-b,0);
127             }
128             else if(a<b){
129                 add(i,t,b-a,0);
130             }
131         }
132         for(int i=1;i<=m;i++){
133             scanf("%d %d %d %lf",&a,&b,&c,&p);
134             if(c>0) add(a,b,1,0);
135             if(c>1) add(a,b,c-1,-log2(1-p));
136         }
137         double ans=MCMF(s,t,n+2);
138         printf("%.2f
",1.0-pow(2,-ans));
139     }
140 }

View Code