E - Water Distribution

---

题目大意：

有\(N\)座城市，给定这\(N\)座城市的坐标和初始的水量\(x_i,y_i,a_i\)，在两个城市之间运水的花费是两个城市的欧几里得距离。最小水量的城市水量最大是多少。
\(N\le 15\)

题目分析：

看数据够小，要么爆搜要么状压。

可以发现这和经典的TSP问题有些类似。

考虑通过构建联通分量来调节水，那么我们设联通分量的城市数量为\(K\)，联通分量中的总水量为\(A\)，联通分量中总的边长是\(B\)，那么不难发现我们能够达到的最大的最小水量就是\(\frac{A-B}{k}\)，因为我们需要花费B的水量而总水量是\(A\)。

我们同样可以证明出一定能够到达\(\frac{A-B}{k}\)，假设我们在点\(X\)和点\(Y\)之间建立了联系，那么如果\(X\)的水的量过大，就可以都运到\(Y\)否则我们就运送到\(X\)。

我们可以通过对每种城市分布都求MST的方法来得出以上我们所需要的。这样的时间复杂度为\(O(2^n*n^2)\)，然后使用枚举子集的方式即可以在\(O(3^n)\)的时间复杂度内通过此题。

#include<bits/stdc++.h> using namespace std; const int N=17; double dis[N][N],f[1<<N],x[N],y[N],a[N]; int n,m; int main() {cin>>n;for(int i=1;i<=n;i++){cin>>x[i]>>y[i]>>a[i];}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));for(int i=0;i<=1<<n;i++) f[i]=1e18;f[0]=0;for(int i=0;i<n;i++) f[1<<i]=0;for(int s=0;s<1<<n;s++){for(int i=0;i<=n-1;i++)for(int j=0;j<=n-1;j++)if((s&(1<<i))&&(!(s&(1<<j)))) f[s|(1<<j)]=min(f[s|(1<<j)],f[s]+dis[i+1][j+1]);}for(int s=0;s<1<<n;s++){f[s]=-f[s];for(int i=0;i<n;i++)if(s&(1<<i)) f[s]+=a[i+1];f[s]/=__builtin_popcount(s);for(int t=(s-1)&s;t;t=(t-1)&s)f[s]=max(f[s],min(f[t],f[s-t]));}printf("%.10lf\n", f[(1<<n)-1]); }

转载于:https://www.cnblogs.com/victorique/p/10060289.html

总结

以上是生活随笔为你收集整理的E - Water Distribution的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。