[CF671D]Roads in Yusland

2019-11-06 06:01:58

字體：大中小

來源：轉載

供稿：網友

題目大意

一顆n個節點的樹所有邊都壞掉了。請m個工人修路，每個工人都可以修一條樹鏈ui到vi，費用為ci。求最小修路費用，無法全部修復輸出-1。

DP

我們來設f[i]表示i子樹全都修好（包括i到父親那條邊）的最小費用。怎么轉移呢？比如有一個能修i到其父親邊的工人j，費用是這個工人的費用+其他雜七雜八的子樹的f值和。用線段樹來維護，大概是這樣吧QAQ

貪心

我們來看看一個強做法！首先可以把修邊看成修點，根節點不用修。設xj表示第j個工人的使用次數，顯然xj>=0 Ai,j=1表示第j個工人能第i個點，否則Ai,j=0 x>=0 $x>=0$ 對于所有1<=i<=n有∑Ai,j?xj>=1，即Ax>=e $對于所有1<=i<=n有/sum Ai,j*xj>=1，即Ax>=e$ min{∑mj=1cj?xj}即min{cTx} $min/{/sum_{j=1}^mcj*xj/}即min/{c^Tx/}$ 我們來轉化為對偶問題 y>=0 $y>=0$ ATy<=c $A^Ty<=c$ max{eTy} $max/{e^Ty/}$ 然后我們就轉化成了這個對偶問題，能不能說人話呢？就是每個點可以選若干次，一個工人的對應路徑上點的選擇次數總和在ci以內，使所有點選的次數和最大。那么我們來貪心吧！自下而上做，每次貪心把這個點選到最大值。代碼怎么寫呢？用set+啟發式合并啊！其實還是不太好想怎么寫的，可以看看我怎么寫哦！

#include<cstdio>#include<algorithm>#include<set>#define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;typedef long long ll;struct dong{ int x,cnt; friend bool Operator <(dong a,dong b){ return a.cnt<b.cnt||a.cnt==b.cnt&&a.x<b.x; }} zlt;const int maxn=300000+10;set<dong> s[maxn];ll c[maxn],ad[maxn];int h[maxn],go[maxn*2],next[maxn*2],root[maxn];int h2[maxn],g2[maxn*2],n2[maxn*2],ca[maxn*2];int i,j,k,l,t,n,m,tot,top;ll ans;bool czy;int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f;}void add(int x,int y){ go[++tot]=y; next[tot]=h[x]; h[x]=tot;}void add2(int x,int y,int z){ g2[++top]=y; ca[top]=z; n2[top]=h2[x]; h2[x]=top;}void dfs(int x,int y){ int t,r,p,z; set<dong>::iterator it; r=root[x]=x; t=h2[x]; while (t){ if (ca[t]==1){ zlt.x=g2[t];zlt.cnt=c[g2[t]]; s[r].insert(zlt); } t=n2[t]; } t=h[x]; while (t){ if (go[t]!=y){ dfs(go[t],x); if (czy) return; p=root[go[t]]; if (s[p].size()>s[r].size()){ it=s[r].begin(); while (it!=s[r].end()){ z=(*it).x; c[z]-=ad[x]; c[z]+=ad[go[t]]; zlt.x=z;zlt.cnt=c[z]; s[p].insert(zlt); it++; } s[r].clear(); r=root[x]=p; ad[x]=ad[go[t]]; } else{ it=s[p].begin(); while (it!=s[p].end()){ z=(*it).x; c[z]-=ad[go[t]]; c[z]+=ad[x]; zlt.x=z;zlt.cnt=c[z]; s[r].insert(zlt); it++; } s[p].clear(); } } t=next[t]; } t=h2[x]; while (t){ if (ca[t]==-1){ zlt.x=g2[t];zlt.cnt=c[g2[t]]; s[r].erase(s[r].find(zlt)); } t=n2[t]; } if (x==1) return; if (s[r].begin()==s[r].end()){ czy=1; return; } z=(*s[r].begin()).cnt-ad[x]; ans+=(ll)z; ad[x]+=(ll)z;}int main(){ n=read();m=read(); fo(i,1,n-1){ j=read();k=read(); add(j,k);add(k,j); } fo(i,1,m){ j=read();k=read(); add2(j,i,1);add2(k,i,-1); c[i]=read(); } dfs(1,0); if (czy)