E - Water Distribution

---

題目大意：

有\(N\)座城市，給定這\(N\)座城市的坐標(biāo)和初始的水量\(x_i,y_i,a_i\)，在兩個(gè)城市之間運(yùn)水的花費(fèi)是兩個(gè)城市的歐幾里得距離。最小水量的城市水量最大是多少。
\(N\le 15\)

題目分析：

看數(shù)據(jù)夠小，要么爆搜要么狀壓。

可以發(fā)現(xiàn)這和經(jīng)典的TSP問(wèn)題有些類似。

考慮通過(guò)構(gòu)建聯(lián)通分量來(lái)調(diào)節(jié)水，那么我們?cè)O(shè)聯(lián)通分量的城市數(shù)量為\(K\)，聯(lián)通分量中的總水量為\(A\)，聯(lián)通分量中總的邊長(zhǎng)是\(B\)，那么不難發(fā)現(xiàn)我們能夠達(dá)到的最大的最小水量就是\(\frac{A-B}{k}\)，因?yàn)槲覀冃枰ㄙM(fèi)B的水量而總水量是\(A\)。

我們同樣可以證明出一定能夠到達(dá)\(\frac{A-B}{k}\)，假設(shè)我們?cè)邳c(diǎn)\(X\)和點(diǎn)\(Y\)之間建立了聯(lián)系，那么如果\(X\)的水的量過(guò)大，就可以都運(yùn)到\(Y\)否則我們就運(yùn)送到\(X\)。

我們可以通過(guò)對(duì)每種城市分布都求MST的方法來(lái)得出以上我們所需要的。這樣的時(shí)間復(fù)雜度為\(O(2^n*n^2)\)，然后使用枚舉子集的方式即可以在\(O(3^n)\)的時(shí)間復(fù)雜度內(nèi)通過(guò)此題。

#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]); }

轉(zhuǎn)載于:https://www.cnblogs.com/victorique/p/10060289.html

總結(jié)

以上是生活随笔為你收集整理的E - Water Distribution的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。