[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) PRintf("-1/n");else printf("%I64d/n",ans);}

上一篇：mybatis报错，元素内容必须由格式正确的字符数据或标记组成

下一篇：easyui东西南北中布局