Description

給定一張n個點m條邊的無向圖，點編號1到n，每個點x有兩個權(quán)值ax和bx。給定k，選出圖中一個大小為k的點集S，使得S中任意兩個點之間存在僅經(jīng)過這個點集中的點的路徑。S也存在兩個權(quán)值aS和bS：aS為S中所有點的ax的最大值；bS為S中所有點的bx的最大值。求最小化aS+bS并輸出這個最小值。

Input

第一行三個數(shù) n,m,k。
接下來n行，第i+1行兩個數(shù)ai和bi。
接下來m行，每行兩個數(shù)x,y表示x和y之間有一條無向邊。保證x和y不相等，任意兩個點之間最多一條邊。

Output

輸出要求的最小值，若無解，輸出“no solution”（引號不輸出）。

Sample Input

5 7 3
1 2
2 1
2 2
1 1
1 2
1 3
4 5
2 3
5 1
4 2
1 4
3 4

Sample Output

3

Data Constraint

Subtask1：1 ≤ n ≤ 20, 1 ≤ m ≤ 100，時間限制1s，分值7。
Subtask2：1 ≤ n, m ≤ 5000，時間限制1s，分值17。
Subtask3：2 ≤ n ≤ 300000, m = n ? 1，保證圖連通，時間限制2s，分值32。
Subtask4：1 ≤ n ≤ 300000, 1 ≤ m ≤ 500000，時間限制3s，分值44。
保證權(quán)值均為正整數(shù)且不超過1,000,000,000。

Solution

• 看到這種有兩個限制的題，先考慮固定一種限制，再想辦法同時處理另一個限制。

• 由于是選擇點集，權(quán)值又在點上不好處理，于是我們可以將權(quán)值轉(zhuǎn)移到邊上：

• 一條邊的邊權(quán) (a,b) 就設(shè)為兩端點的 (a,b) max起來： (max(a1,a2),max(b1,b2))

• 那么選了一條邊就相當(dāng)于選了其兩個端點，這樣就方便多了。

• 先將 a 和 b 的值離散化，從小到大排序。

• 設(shè) mxa 和 mxb ，那么答案即為 ans=min(ans,mxa+mxb) 。

• 我們使 mxa 從小到大的依次增加（開始時使 mxb 為最大的 b），

• 每次把當(dāng)前 mxa 對應(yīng)的邊加入圖中（用邊集數(shù)組連邊即可），

• 我們發(fā)現(xiàn)可以像維護最小生成樹那樣，加入小邊，刪去之前較大的邊（LCT維護）（問題①）。

• 即：若該邊的 b 小于樹中邊最大的 b ，就用該邊替換之，否則就不加入。

• 若某個時刻加邊后連通塊大小 ≥k 就可以更新答案了。

• 這時我們就將 mxb 減少，并刪去樹中對應(yīng)的邊（沒有就不刪），

• 這樣繼續(xù)更新答案，知道刪到某一個 mxb 中的邊后連通塊大小 <k<script type="math/tex" id="MathJax-Element-5385">mxb 了，

• 之后就繼續(xù)增加 mxa ，重復(fù)以上操作。

• 現(xiàn)在解決 問題①：為什么這樣就是正確的呢？

• 因為刪去 b 值較大的邊，（在 mxb 減少時它會先被刪），就盡可能保持了它之后的連通性。

• 因為 mxa 和 mxb 都是單調(diào)的，于是時間復(fù)雜度就是 O(N?log?N) 。

Code

#include<cstdio> #include<algorithm> #include<map> #include<cctype> using namespace std; const int N=3e5+5,M=N*3,inf=2e9+1; struct data {int x,y,a,b; }c[M]; int n,m,k,na,nb,tot1,tot2,cnta,cntb,top,ans=inf; int firsta[M],nexa[M],ena[M]; int firstb[M],nexb[M],enb[M]; int a[N],b[N],aa[M],bb[M]; int fa[M],size[M],sz[M],s[M][2],num[M],mx[M],st[M]; bool rev[M],bz[M]; map<int,int>mpa,mpb; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline bool isroot(int x) {return x^s[fa[x]][0] && x^s[fa[x]][1]; } inline void reverse(int x) {if(x) swap(s[x][0],s[x][1]),rev[x]^=1; } inline bool update(int x) {size[x]=size[s[x][0]]+size[s[x][1]]+1+sz[x];num[x]=mx[num[s[x][0]]]>mx[num[s[x][1]]]?num[s[x][0]]:num[s[x][1]];if(mx[x]>mx[num[x]]) num[x]=x; } inline void down(int x) {if(rev[x]){reverse(s[x][0]),reverse(s[x][1]);rev[x]=false;} } inline void rotate(int x) {int y=fa[x],w=pd(x);if((fa[x]=fa[y]) && !isroot(y)) s[fa[y]][pd(y)]=x;if(s[y][w]=s[x][w^1]) fa[s[y][w]]=y;s[fa[y]=x][w^1]=y;update(y); } inline void splay(int x) {for(int y=st[top=1]=x;!isroot(y);y=fa[y]) st[++top]=fa[y];while(top) down(st[top--]);for(int y;!isroot(x);rotate(x))if(!isroot(y=fa[x])) rotate(pd(x)==pd(y)?y:x);update(x); } inline void access(int x) {for(int y=0;x;x=fa[y=x]){splay(x);sz[x]+=size[s[x][1]];sz[x]-=size[s[x][1]=y];update(x);} } inline void mkroot(int x) {access(x),splay(x),reverse(x); } inline void link(int x,int y) {mkroot(x),mkroot(y);sz[fa[x]=y]+=size[x];update(y); } inline void cut(int x,int y) {mkroot(x),access(y),splay(y);s[y][0]=fa[x]=0; } inline bool connect(int x,int y) {mkroot(x),access(y),splay(y);int z=y;while(s[z][0]) z=s[z][0];return x==z; } inline void inserta(int x,int y) {nexa[++tot1]=firsta[x];firsta[x]=tot1;ena[tot1]=y; } inline void insertb(int x,int y) {nexb[++tot2]=firstb[x];firstb[x]=tot2;enb[tot2]=y; } inline void insa(int x,int pos) {if(!mpa[x]) mpa[x]=++cnta;inserta(mpa[x],pos); } inline void insb(int x,int pos) {if(!mpb[x]) mpb[x]=++cntb;insertb(mpb[x],pos); } int main() {n=read(),m=read(),k=read();for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(),size[i]=1;if(k==1){int sum=inf;for(int i=1;i<=n;i++) sum=min(sum,a[i]+b[i]);return 0&printf("%d",sum);}for(int i=1;i<=m;i++){c[i].x=read(),c[i].y=read();c[i].a=max(a[c[i].x],a[c[i].y]);c[i].b=max(b[c[i].x],b[c[i].y]);insa(c[i].a,i);insb(c[i].b,i);aa[i]=c[i].a,bb[i]=c[i].b;}sort(aa+1,aa+1+m);sort(bb+1,bb+1+m);na=unique(aa+1,aa+1+m)-(aa+1);nb=unique(bb+1,bb+1+m)-(bb+1);int mxb=nb;for(int i=1;i<=na;i++){for(int j=firsta[mpa[aa[i]]];j;j=nexa[j]){int nn=ena[j],x=c[nn].x,y=c[nn].y,z=nn+n;if(bz[nn]) continue;mx[num[z]=z]=c[nn].b;if(!connect(x,y)) link(x,z),link(z,y); else{mkroot(x),access(y),splay(y);if(c[nn].b<mx[num[y]]){int pos=num[y];cut(c[pos-n].x,pos);cut(pos,c[pos-n].y);link(x,z),link(z,y);}}mkroot(x),access(y),splay(y);while(size[y]>=k+k-1){ans=min(ans,aa[i]+bb[mxb]);for(int l=firstb[mpb[bb[mxb]]];l;l=nexb[l]){int nn1=enb[l],xx=c[nn1].x,yy=c[nn1].y;bz[nn1]=true;if(connect(xx,yy)){mkroot(xx),access(yy),splay(yy);int pos=num[yy];cut(c[pos-n].x,pos);cut(pos,c[pos-n].y);}}if(!--mxb){if(ans==inf) puts("no solution"); else printf("%d",ans);return 0;}mkroot(x),access(y),splay(y);}}}if(ans==inf) puts("no solution"); else printf("%d",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5643. 【NOI2018模拟4.10】最小代价的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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