本文主要是介绍hdu5988 2016icpc青岛站 G题 Coding Contest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接 点击打开链接
比赛的时候T了两个小时也没出来。。。本来以为是模板的锅，然而下来用zkw还是T出翔，发现真的是eps的锅。。。还有就是把乘利用对数变成加。。。（神技）
题目意思大概是给你n个块，每一个块里面有s[i]个acmer，有b[i]份食物，到了午饭时间，所有人都要吃午饭，但是每一个块里的食物有限，所以他们要移动到其他块里，但是路上有网线，每走一次就有p的概率把网线碰断，导致网络奔溃（某条路第一次走的时候一定不会被破坏）。
#include<cmath>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;const int MAXN=300;
const int MAXE=100000;
const int INF=2e9;
const double eps = 1e-8;
struct Edge
{int from;int to;int next;int re;//记录逆边的下标int cap;//容量double cost;//费用
}edge[MAXE];
int pre[MAXN];
int head[MAXN];
bool vis[MAXN];
int que[MAXN];
double dist[MAXN];
int tol;//边的总数
void add(int u,int v,int ca,double co)
{edge[tol].from=u;edge[tol].to=v;edge[tol].cap=ca;edge[tol].cost=co;edge[tol].re=tol+1;edge[tol].next=head[u];head[u]=tol++;edge[tol].from=v;//加逆边edge[tol].to=u;edge[tol].cap=0;edge[tol].cost=-co;edge[tol].re=tol-1;edge[tol].next=head[v];head[v]=tol++;
}
int N;
int start;
int T;
bool SPFA()
{int front=0,rear=0;for(int v=0;v<=N;v++){if(v==start){que[rear++]=v;vis[v]=true;dist[v]=0;}else{dist[v]=INF;vis[v]=false;}}memset(pre,-1,sizeof(pre));while(front!=rear){int u=que[front++];vis[u]=false;if(front>=MAXN)front=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(edge[i].cap&&dist[v]-dist[u]-edge[i].cost > eps){dist[v]=dist[u]+edge[i].cost;pre[v]=i;if(!vis[v]){que[rear++]=v;vis[v]=true;if(rear>=MAXN)rear=0;}}}}if(pre[T] == -1)return false;return true;
}
double c;//费用
int f;//最大流void minCostMaxflow()
{f=0;c = 0;int u,p;while(SPFA()){int Min=INF;for(u=T;u!=start;u=edge[p].from){p=pre[u];Min=min(Min,edge[p].cap);}for(u=T;u!=start;u=edge[p].from){p=pre[u];edge[p].cap-=Min;edge[edge[p].re].cap+=Min;}c+=dist[T]*Min;f+=Min;}
}struct node
{int x,y,z;
}a[110];
int main()
{int t,n,m,i;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);a[i].z = a[i].x - a[i].y;}start=0;N=n+1;T=n+1;tol=0;memset(head,-1,sizeof(head));for(i=1;i<=m;i++){int x,y,c;double p;scanf("%d%d%d%lf",&x,&y,&c,&p);p = -log2(1.0-p);if(c > 0)add(x,y,1,0);if(c - 1 > 0)add(x,y,c-1,p);}for(int i=1;i<=n;i++){if(a[i].z > 0)add(start,i,a[i].z,0);else if(a[i].z < 0)add(i,T,-a[i].z,0);}minCostMaxflow();double ans = 1 - pow(2,-c);printf("%.2f\n",ans);}return 0;
}
这篇关于hdu5988 2016icpc青岛站 G题 Coding Contest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
