正題

題目鏈接:https://jzoj.net/senior/#contest/show/3002/1

---

題目大意

$n$個點$m$條邊，每條邊有$(u,v)$兩個權值。

$q$個詢問，每次詢問一個$(k1,k2)$，將所有邊的權值變為$u?k1+v?k2$后求最小生成樹。

---

解題思路

首先$u?k1+v?k2?(u+v?\frac{k2}{k1})?k1$，所以決策可以線性表示出來。

我們考慮維護一個坐標系$(x,y)$表示$u$值和為$x$的生成樹中$y$值和最小是多少。

顯然$x$增大時$y$在減小，所以這是一個下突殼。

考慮維護這一個突殼，首先是兩個端點$l:(k1=0,k2=1)$時和$r:(k1=1,k2=0)$各做一次最小生成樹，此時我們考慮找到一個在線段$(l,r)$的左下角最遠的點$mid$。

通過差積各種證明后我們發現有$mid(k1=|y_l?y_r|,k2=|x_l?x_r|)$，然后分治下去處理$(l,mid)$和$(r,mid)$。

當$mid$在線段$(l,r)$上時，證明左下角已經沒有更優的點，所以可以返回了。

最后在突殼上三分答案就好了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int M=25100,N=40; struct node{int x,y;double u,v; }a[M]; struct knode{double k1,k2,x,y; }k[M*4],head,tail; int n,m,q,fa[N],tot; double k1,k2; int find(int x) {return fa[x]==x?x:(fa[x]=find(fa[x]));} bool cmp(node x,node y) {return x.u*k1+x.v*k2<y.u*k1+y.v*k2;} void Get_Tree(knode &k){k1=k.k1;k2=k.k2;k.x=k.y=0;sort(a+1,a+1+m,cmp);for(int i=1;i<=n;i++)fa[i]=i;int z=n;for(int i=1;i<=m;i++){int fx=find(a[i].x),fy=find(a[i].y);if(fx!=fy){if(fx>fy) swap(fx,fy);fa[fy]=fx;z--;k.x+=a[i].u;k.y+=a[i].v;}}return; } void Solve(knode l,knode r){knode mid;mid.k1=fabs(r.y-l.y);mid.k2=fabs(r.x-l.x);Get_Tree(mid);if(l.y==mid.y||l.y==r.y||(l.x-r.x)/(l.y-r.y)==(l.x-mid.x)/(l.y-mid.y))return;Solve(l,mid);k[++tot]=mid;Solve(mid,r); } int main() {scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=m;i++)scanf("%d%d%lf%lf",&a[i].x,&a[i].y,&a[i].u,&a[i].v);head.k1=1;tail.k2=1;Get_Tree(head);Get_Tree(tail);k[tot=1]=head;Solve(head,tail);k[++tot]=tail;while(q--){scanf("%lf%lf",&k1,&k2);int l=1,r=tot;double ans=1e18;while(l<r){if(r-l<=2)break;int mid1=l+(r-l+1)/3,mid2=l+(r-l+1)/3*2;if(k[mid1].x*k1+k[mid1].y*k2<k[mid2].x*k1+k[mid2].y*k2) r=mid2;else l=mid1;}for(int i=l;i<=r;i++)ans=min(k[i].x*k1+k[i].y*k2,ans);printf("%.3lf\n",ans);} }

總結

以上是生活随笔為你收集整理的jzoj3860-地壳运动(mst)【最小生成树,三分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。