首页 > 代码库 > BZOJ1812 [IOI2005]river
BZOJ1812 [IOI2005]river
传送门：
很常规的一道树规，转为左儿子右兄弟。
然后f[node][anc][K]表示在node节点上，最近的有贡献祖先在anc上，在node的儿子和兄弟上有k个有贡献节点的最优值。
然后得出以下转移方程。
f[node][anc][K]=min{f[son[node]][anc][k]+f[bro[node]][anc][K-k]}+Value[node]*(dis[node]-dis[anc]); 无贡献
f[node][anc][K]=min{f[son[node]][node][k]+f[bro[node]][anc][K-1-k]} 有贡献
下面是代码实现：
1 //BZOJ 1812 2 //by Cydiater 3 //2016.9.5 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cstring> 8 #include <string> 9 #include <algorithm>10 #include <queue>11 #include <map>12 #include <ctime>13 #include <cmath>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 const int MAXN=105;20 const int oo=0x3f3f3f3f;21 inline int read(){22 char ch=getchar();int x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 int N,K,son[MAXN],bro[MAXN],Value[MAXN],dis[MAXN],LINK[MAXN],len=0,fa[MAXN],f[MAXN][MAXN][MAXN],pre_fa[MAXN];28 struct edge{29 int y,next,v;30 }e[MAXN<<1];31 namespace solution{32 inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}33 void dfs(int node){34 for(int i=LINK[node];i;i=e[i].next){35 dis[e[i].y]=dis[node]+e[i].v;36 dfs(e[i].y);37 }38 }39 void init(){40 N=read();K=read();41 pre_fa[0]=-1;42 up(i,1,N){43 Value[i]=read();int y=read(),v=read();44 pre_fa[i]=y;45 insert(y,i,v);46 }47 dfs(0);dis[0]=0;48 }49 void build(int node,int father){50 int tmp=LINK[node];son[node]=e[tmp].y;fa[node]=father;51 if(tmp)build(e[tmp].y,node);node=e[tmp].y;52 for(int i=e[tmp].next;i;i=e[i].next){53 bro[node]=e[i].y;build(e[i].y,node);54 node=e[i].y;55 }56 }57 void TreeDP(int node){58 if(son[node])TreeDP(son[node]);59 if(bro[node])TreeDP(bro[node]);60 int father=pre_fa[node];61 while(father!=-1){62 up(lim,0,K)up(k,0,lim){63 int tmp=Value[node]*(dis[node]-dis[father]);64 if(son[node])tmp+=f[son[node]][father][k];65 if(bro[node])tmp+=f[bro[node]][father][lim-k];66 f[node][father][lim]=min(f[node][father][lim],tmp);67 }68 up(lim,1,K)up(k,1,lim){69 int tmp=0;70 if(son[node])tmp+=f[son[node]][node][k-1];71 if(bro[node])tmp+=f[bro[node]][father][lim-k];72 f[node][father][lim]=min(f[node][father][lim],tmp);73 }74 father=pre_fa[father];75 }76 if(node==0){77 father=0;78 up(lim,0,K)up(k,0,lim){79 int tmp=0;80 if(son[node])tmp+=f[son[node]][father][k];81 if(bro[node])tmp+=f[bro[node]][father][lim-k];82 f[node][father][lim]=min(f[node][father][lim],tmp);83 }84 }85 }86 void slove(){87 build(0,-1);88 memset(f,0x3f,sizeof(f));89 TreeDP(0);90 printf("%d\n",f[0][0][K]);91 }92 }93 int main(){94 //freopen("input.in","r",stdin);95 using namespace solution;96 init();97 slove();98 return 0;99 }
BZOJ1812 [IOI2005]river
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。