[CF671D]Roads in Yusland

3/8/2017来源:ASP.NET技巧人气:1078

题目大意

一颗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 对于所有1<=i<=n有∑Ai,j∗xj>=1,即Ax>=e min{∑mj=1cj∗xj}即min{cTx} 我们来转化为对偶问题 y>=0 ATy<=c max{eTy} 然后我们就转化成了这个对偶问题,能不能说人话呢? 就是每个点可以选若干次,一个工人的对应路径上点的选择次数总和在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) PRintf("-1\n");else printf("%I64d\n",ans); }