网站悬浮广告代码,陕西华伟建设有限公司网站,网站建设图片滑动代码,简速做网站题面#xff1a;[USACO 2001 OPEN]地震 题目描述#xff1a; 一场地震把约翰家的牧场摧毁了#xff0c; 坚强的约翰决心重建家园。 约翰已经重建了N个牧场#xff0c;现在他希望能修建一些道路把它们连接起来。研究地形之后#xff0c;约翰发现可供修建的道路有M条。碰巧的…题面[USACO 2001 OPEN]地震 题目描述 一场地震把约翰家的牧场摧毁了 坚强的约翰决心重建家园。 约翰已经重建了N个牧场现在他希望能修建一些道路把它们连接起来。研究地形之后约翰发现可供修建的道路有M条。碰巧的是奶牛们最近也成立一个工程队专门从事修复道路。而然奶牛们很有经济头脑如果无利可图它们是不会干的。 奶牛们关注的是挣钱速度即总利润和总施工时间的比值。约翰和奶牛达成了协议奶牛负责修建道路将所有牧场连通而约翰需要支付F元。每条道路都有自己的施工时间和建造成本。连接两个相同的牧场的道路可能有多条。保证所有的牧场必定是可连通的不过也有可能一些道路的建造成本之和会超过F。 请帮助奶牛们选择修复哪些道路才能使单位时间的利润最大 输入格式 第一行三个整数 NM和F\(1 ≤ N ≤ 400\)\(1 ≤ M ≤ 10000\)\(1 ≤ F ≤ 2 × 10^9\) 第二行到\(M 1\)行第\(i 1\)行表示第i条道路的信息有四个整数\(U_i\) \(V_i\) \(C_i\) 和\(T_i\) \(U_i\) 和\(V_i\) 表示这条道路连接的牧场编号Ci表示道路修建的成本Ti表示道路修建所需要的时间\(1 ≤ U_i ≤ N\)\(1 ≤ V_i ≤ N\)$1 ≤ C_i ≤ 2 × 10^9 $\(1 ≤ T_i ≤ 2 × 10^9\) 输出格式 第一行一个保留四位小数的浮点数表示奶牛们能挣到的最大单位时间利润如果奶牛们无钱可赚则输出0.0000 输入样例#1 5 5 100 1 2 20 5 1 3 20 5 1 4 20 5 1 5 20 5 2 3 23 1 输出样例#1 1.0625 说明: 奶牛们可以选择连通最后四条道路则总时间为 16总成本为 83所以单位利润为17/16 1.0625 \(solution:\) 这题其实牵扯到了一种普遍的二分答案的方法与我等下会讲的HNOI2009 最小圈 一样有许多的共同点。因为这些题要求我们输出的ans都是针对权值总和不断计算而来的。本题就是个经典例题二分答案求最优比率生成树因为我们可以直接通过题意看出它要求我们输出的最终答案实际上就是 $ans \frac{F-\sum{v_i} \quad (i\in S)}{\sum{t_i}\quad (i\in S)} $ 其中S为我们最终所选择的最优生成树的边权的集合我们将这个式子转换一下可以得到 \(Fans*\sum{t_i}\sum{v_i}\) \(F\sum{ans*t_iv_i}\quad _{(i\in S)}\) 注这一点我们一定要清楚此时等式右边就是生成树只不过树边权变成了\(ans*t_iv_i\) 上述式子中我们的ans就是我们最终要输出的最优比率这个ans是我们可以二分得到的因为答案具有单调性当然这个需要我们进一步证明首先因为ans是最优比率那么我们可以知道对于图上的任意一个生成树的边的集合K一定有$\frac{F-\sum{v_i} \quad (i\in K)}{\sum{t_i}\quad (i\in K)}\leq ans $ 根据上述方式转化得\(F\leq \sum{ans*t_iv_i}\quad {(i\in K)}\)只有当我们的集合K取到最优的生成树时也就是KS的时候这个式子才会是等式然后我们来证明二分的正确性当我们二分求ans的时候对于我们当前的比率x一定有这三种情况 \(1.\) \(xans\) 当我们比率为ans时\(F\leq \sum{ans*t_iv_i}\quad {(i\in K )}\) 现在我们的比率x比ans还大那我们的肯定有\(F \sum{x*t_iv_i}\quad {(i\in K)}\) \(2.\) \(xans\) 我已经说过了\(F\leq\sum{ans*t_iv_i}\quad {(i\in K)}\) \(3.\) \(xans\) 这个时候我们发现我们不能确认\(F\) 和 \(\sum{ans*t_iv_i}\quad {(i\in K)}\) 的大小关系了因为我们的K是任意生成树的边的集合此时我们小于等于大于都有可能但也正是如此我们可以证明一定存在一个边的集合满足\(F\sum{x*t_iv_i}\quad {(i\in S)}\)因为就拿我们ans情况下的最优边集S因为 \(F\sum{ans*t_iv_i}\quad {(i\in S)}\) 此时我们的\(xans\) 所以\(F\sum{x*t_iv_i}\quad {(i\in S)}\) 如何二分为什么用最小生成树 那我们证明了上面这个东西有什么用呢根据上述三个关系的特性就是那三个不等式我们发现当我们将x带进去后只要求得最小的 \(\sum{ans*t_iv_i}\quad {(i\in K)}\) 我们就可以直接判断出x和ans的关系了 我们将最小的\(\sum{ans*t_iv_i}\quad {(i\in K)}\) 看做min 若\(Fmin\)则必有\(F \sum{x*t_iv_i}\quad {(i\in K)}\) 这不就是第一种情况吗x必然大于ans若\(Fmin\)则必有\(F \leq \sum{x*t_iv_i}\quad {(i\in K)}\) 这不就是第一种情况吗x必然等于ans若\(Fmin\)则x必然不大于也不等于ans那不就是小于ans吗证过了若xans则必存在一个K\(F\sum{x*t_iv_i}\quad {(i\in K)}\)那我们如何求最小的\(\sum{x*t_iv_i}\quad {(i\in K)}\) 呢 这就是求最小生成树嘛只不过树边权变成了\(ans*t_iv_i\)我们每一次都重新排个序就行了 总复杂度\(O(m *logm*log(r-l1))\) \(code:\) #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset#define ll long long
#define db double
#define rg register intusing namespace std;const db cha1e-9;struct su{int x,y,v,t;db k;
}a[10005];int n,m,f;
int s[405];inline int qr(){char ch;while((chgetchar())0||ch9);int resch^48;while((chgetchar())0ch9)resres*10(ch^48);return res;
}inline bool cmp(su x,su y){return x.ky.k;}inline int get(int x){if(s[x]x)return x;return s[x]get(s[x]);
}inline bool check(db x){db res0;for(rg i1;in;i)s[i]i;//并查集for(rg i1;im;i)a[i].kx*a[i].t(db)a[i].v;//更新边权sort(a1,am1,cmp);//kruskal求最小生成树for(rg i1;im;i)if(get(a[i].x)!get(a[i].y))resa[i].k,s[get(a[i].x)]get(a[i].y);//求新边权的总和return fres?0:1;
}int main(){freopen(quake.in,r,stdin);freopen(quake.out,w,stdout);nqr(),mqr(),fqr();for(rg i1;im;i)a[i]su{qr(),qr(),qr(),qr()};if(check(0))puts(0.0000),exit(0);//特判db l0,r1e14,mid;while(r-lcha){//二分答案mid(lr)/2;if(check(mid))rmid-cha;else lmidcha;}printf(%.4lf,l);return 0;
}转载于:https://www.cnblogs.com/812-xiao-wen/p/10367014.html
