亿玫网站建设,北京企业服务e窗通平台,变性WordPress,深圳市工程交易中心3130: [Sdoi2013]费用流 Time Limit: 10 Sec Memory Limit: 128 MBSec Special JudgeSubmit: 960 Solved: 505[Submit][Status][Discuss]Description Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。 最大流问题#xff1a;给定一张有向图表示运输网络… 3130: [Sdoi2013]费用流 Time Limit: 10 Sec Memory Limit: 128 MBSec Special JudgeSubmit: 960 Solved: 505[Submit][Status][Discuss] Description Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。 最大流问题给定一张有向图表示运输网络一个源点S和一个汇点T每条边都有最大流量。一个合法的网络流方案必须满足(1)每条边的实际流量都不超过其最大流量且非负(2)除了源点S和汇点T之外对于其余所有点都满足该点总流入流量等于该点总流出流量而S点的净流出流量等于T点的净流入流量这个值也即该网络流方案的总运输量。最大流问题就是对于给定的运输网络求总运输量最大的网络流方案。 上图表示了一个最大流问题。对于每条边右边的数代表该边的最大流量左边的数代表在最优解中该边的实际流量。需要注意到一个最大流问题的解可能不是唯一的。 对于一张给定的运输网络Alice先确定一个最大流如果有多种解Alice可以任选一种之后Bob在每条边上分配单位花费单位花费必须是非负实数要求所有边的单位花费之和等于P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到Bob在分配单位花费之前已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小而Bob希望总费用尽量大。我们想知道如果两个人都执行最优策略最大流的值和总费用分别为多少。 Input 第一行三个整数NMP。N表示给定运输网络中节点的数量M表示有向边的数量P的含义见问题描述部分。为了简化问题我们假设源点S是点1汇点T是点N。 接下来M行每行三个整数ABC表示有一条从点A到点B的有向边其最大流量是C。 Output 第一行一个整数表示最大流的值。第二行一个实数表示总费用。建议选手输出四位以上小数。 Sample Input 3 2 1 1 2 10 2 3 15 Sample Output 10 10.0000 HINT 【样例说明】 对于Alice最大流的方案是固定的。两条边的实际流量都为10。 对于Bob给第一条边分配0.5的费用第二条边分配0.5的费用。总费用为10*0.510*0.510。可以证明不存在总费用更大的分配方案。【数据规模和约定】 对于20%的测试数据所有有向边的最大流量都是1。 对于100%的测试数据N 100M 1000。 对于l00%的测试数据所有点的编号在I..N范围内。1 每条边的最大流量 50000。1 P 10。给定运输网络中不会有起点和终点相同的边。 第一问不用说了假设现在已经有了一个最大流的方案那么Bob一定会把 P 的费用全用到流量最大的那条边上也就是说要让最大流量的边最小二分边的最大流看检查是否还能求得同样大小的最大流注意要实数二分不能整数二分 最大流本身是一定的整数但是为满足最优解某一条边的流量可以是实数。所以这题是实数网络流 实数二分好坑.........不要m-1不要保留一个ans只是简单的二分l和r行了最后取那一个都行 //
// main.cpp
// sdoi2003费用流
//
// Created by Candy on 25/11/2016.
// Copyright © 2016 Candy. All rights reserved.
//#includeiostream
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N105,M1005,INF1e9;
const double eps1e-5;
int read(){char cgetchar();int x0,f1;while(c0||c9){if(c-)f-1; cgetchar();}while(c0c9){xx*10c-0; cgetchar();}return x*f;
}
int n,m,p,u,v,c,s,t;
struct data{int u,v,c;
}a[M];
struct edge{int v,ne;double c,f;
}e[M1];
int h[N],cnt0;
inline void ins(int u,int v,double c){cnt;e[cnt].vv;e[cnt].cc;e[cnt].f0;e[cnt].neh[u];h[u]cnt;cnt;e[cnt].vu;e[cnt].c0;e[cnt].f0;e[cnt].neh[v];h[v]cnt;
}
void build(double mid){cnt0;memset(h,0,sizeof(h));for(int i1;im;i) ins(a[i].u,a[i].v,min((double)a[i].c,mid));
}
int cur[N];
int d[N],vis[N],q[N],head,tail;
bool bfs(){memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));headtail1;d[s]0;vis[s]1;q[tail]s;while(head!tail){int uq[head];for(int ih[u];i;ie[i].ne){int ve[i].v;if(!vis[v]e[i].ce[i].f){d[v]d[u]1;vis[v]1;q[tail]v;if(vt) return 1;}}}return 0;
}double dfs(int u,double a){if(ut||a0) return a;double flow0,f;for(int icur[u];i;ie[i].ne){int ve[i].v;if(d[v]d[u]1(fdfs(v,min(a,e[i].c-e[i].f)))0){flowf;e[i].ff;e[((i-1)^1)1].f-f;a-f;if(a0) break;}}return flow;
}
double dinic(){double flow0;while(bfs()){for(int i1;in;i) cur[i]h[i];flowdfs(s,INF);}return flow;
}
int main(int argc, const char * argv[]) {nread();mread();pread();s1;tn;double l0,r0;for(int i1;im;i){a[i].uread(),a[i].vread(),a[i].cread();ins(a[i].u,a[i].v,a[i].c);rmax(r,(double)a[i].c);}//reps;double olddinic();while(r-leps){double mid(lr)*0.5;//printf(%f %f\n,l,r);build(mid);double mxdinic();if(fabs(mx-old)eps) rmid;else lmid;}printf(%d\n%.4f,(int)old,l*p);return 0;
} 转载于:https://www.cnblogs.com/candy99/p/6103372.html
