锐客网

  1. 首页 > it技术 > >

HDU|HDU-5988 Coding Contest 最大费用流


Coding Contest 杨神给我讲的题意。。
题意：有n个点，每个点有s个人和b份食物，如果某个点食物不够，那么这个点的人应该去其他的点寻找食物，给出m条路线，表示两个点u、v之间最多能过c个人，且这条路上有电线，第一个人过不会碰坏，但后面的人过都有p的概率会碰坏。求整个网络坏的最小概率。

很典型的费用流模型，人数也就是流量最大的前提下费用尽可能少。但我们直接求整个网络的最小坏的概率是求不出来的，因为一条路坏的概率是p，一个人过去是p，那么两个人呢？所以我们可以求出整个网络不坏的概率，且让其最大即可，这就是最大费用最大流。我们把不坏的概率作为cost传过去，返回值取反即可。
但概率是累乘的，而不是累加的，所以要先用log函数转化一下，这样费用相加就相当于概率相乘，这也是这个题的精妙所在，还有一个不常见的问题，spfa那里松弛操作要加上eps。
用kuangbin的模板很容易超时，多交几发就就就。。。。还是会超时。
【HDU|HDU-5988 Coding Contest 最大费用流】998ms 险过，也许是人品吧。

const double eps=1e-8; const double PI=acos(-1.0); const int INF=1e9+10; const int MOD=1e9+7; const int N=1e3+10; struct Edge { int to,next,cap,flow; double cost; }e[N*20]; int n,m,head[150],tot; int pre[N],vis[200]; double dis[N]; int tn; void init(int num) { tn=num; tot=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int cap,double cost) { e[tot].to=v,e[tot].cap=cap,e[tot].cost=cost,e[tot].flow=0,e[tot].next=head[u]; head[u]=tot++; e[tot].to=u,e[tot].cap=0,e[tot].cost=-cost,e[tot].flow=0,e[tot].next=head[v]; head[v]=tot++; } bool spfa(int s,int t) { queueq; for(int i=0; ie[i].flow&&dis[v]>dis[u]+e[i].cost+eps) { dis[v]=dis[u]+e[i].cost; pre[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(pre[t]==-1) return false; return true; } double mincostMaxflow(int s,int t) { double cost=0; while(spfa(s,t)) { int Min=INF; for(int i=pre[t]; i+1; i=pre[e[i^1].to]) if(Min>e[i].cap-e[i].flow) Min=e[i].cap-e[i].flow; for(int i=pre[t]; i+1; i=pre[e[i^1].to]) { e[i].flow+=Min; e[i^1].flow-=Min; cost+=e[i].cost*Min; } } return -cost; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(n+2); int st=0,en=n+1; double EPS=-log2(1.0); for(int i=1; i<=n; i++) { int s,b; scanf("%d%d",&s,&b); int x=min(s,b); s-=x,b-=x; if(s>0) add(st,i,s,EPS); if(b>0) add(i,en,b,EPS); } int u,v,c; double p; for(int i=1; i<=m; i++) { scanf("%d%d%d%lf",&u,&v,&c,&p); if(c>=1) { add(u,v,1,EPS); if(c>1) add(u,v,c-1,-log2(1-p)); } } double ans=mincostMaxflow(st,en); printf("%.2f\n",1-pow(2.0,ans)); } return 0; }

    推荐阅读


    上一篇：【面试题】第一个只出现一次的字符（三种解法）

    下一篇：高通Android平台下关于display部分的几个关键问题