Coding Contest

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

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

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

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

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

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

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              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

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

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\n",1.0-pow(2,-ans));139 }140 }

View Code

转载于:https://www.cnblogs.com/Fighting-sh/p/9839866.html

你可能感兴趣的文章