T1 [HAOI2010]软件安装
https://daniu.luogu.org/problem/show?pid=2515
树上背包，如果有i必须有j，j作为i的父节点
O（nm²）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 101
#define M 501
using namespace std;
int y[N],h[N],x[N];
int dfn[N],low[N],st[N],top,tot;
bool vis[N];
int cnt,ny[N],nh[N],col[N];
int dp[N][M],m;
int to[M],nxt[M],front[N];
int to2[M],nxt2[M],front2[M];
void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}
void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
}
void add2(int u,int v)
{
to2[++tot]=v; nxt2[tot]=front2[u]; front2[u]=tot;
}
void tarjan(int u)
{
dfn[u]=low[u]=++tot;
vis[u]=true;
st[++top]=u;
if(x[u])
{
if(!dfn[x[u]]) tarjan(x[u]),low[u]=min(low[u],low[x[u]]);
else if(vis[x[u]]) low[u]=min(low[u],dfn[x[u]]);
}
if(dfn[u]==low[u])
{
cnt++;
while(st[top]!=u)
{
ny[cnt]+=y[st[top]];
nh[cnt]+=h[st[top]];
vis[st[top]]=false;
col[st[top]]=cnt;
top--;
}
ny[cnt]+=y[u];
nh[cnt]+=h[u];
vis[u]=false;
col[u]=cnt;
top--;
}
}
void dfs(int now)
{
for(int i=ny[now];i<=m;i++) dp[now][i]=nh[now];
for(int i=front2[now];i;i=nxt2[i])
{
dfs(to2[i]);
for(int j=m;j>=ny[now];j--)
for(int k=;k<=j-ny[now];k++)
dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[to2[i]][k]);
}
}
int main()
{
int n;
read(n); read(m);
for(int i=;i<=n;i++) read(y[i]);
for(int i=;i<=n;i++) read(h[i]);
for(int i=;i<=n;i++)
{
read(x[i]);
add(x[i],i);
}
tot=;
for(int i=;i<=n;i++)
if(!dfn[i]) tarjan(i);
memset(vis,false,sizeof(vis));
tot=;
for(int i=;i<=n;i++)
if(col[i]!=col[x[i]])
add2(col[x[i]],col[i]),vis[col[i]]=true;
for(int i=;i<=cnt;i++)
if(!vis[i]) add2(,i);
dfs();
printf("%d",dp[][m]);
}
可以优化值O（nm），即每次都将要处理的子树和根节点看做一个整体
在dfs子树前，将根节点的值赋值给子节点
具体参考XCH的《浅谈几类背包问题》
https://wenku.baidu.com/view/d59b42fe04a1b0717fd5dd72.html
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=,maxm=;
struct edge
{
int u,v;
};
struct edge Edge[maxn];
int bel[maxn],n,m,col,hi[maxn],yi[maxn],head[maxn],tag,dp[maxn][maxm];
int E[maxn<<],V[maxn<<],cnt,ci[maxn],vi[maxn],dfn[maxn],low[maxn];
int sta[maxn],top,num;
bool vis[maxn];
inline void in(int &now)
{
char Cget;now=;while((Cget=getchar())>''||Cget<'');
while(Cget>=''&&Cget<='')now=now*+Cget-'',Cget=getchar();
}
void tarjan(int now)
{
dfn[now]=low[now]=++tag,sta[++top]=now;
for(int i=head[now];i;i=E[i])
if(!bel[V[i]])
if(dfn[V[i]]) low[now]=min(low[now],dfn[V[i]]);
else tarjan(V[i]),low[now]=min(low[now],low[V[i]]);
if(low[now]==dfn[now])
{
col++;
while(sta[top]!=now)
{
bel[sta[top]]=col;
vi[col]+=yi[sta[top]];
ci[col]+=hi[sta[top]];
top--;
}
bel[now]=col,vi[col]+=yi[now],ci[col]+=hi[now],top--;
}
}
void dfs(int now,int lit)
{
if(lit<=) return;
int v;
for(int i=head[now];i;i=E[i])
if(lit>=vi[V[i]])
{
v=V[i];
for(int e=;e<=lit;e++)
dp[v][e]=dp[now][e];
dfs(v,lit-vi[v]);
for(int e=lit;e>=vi[v];e--)
dp[now][e]=max(dp[now][e],dp[v][e-vi[v]]+ci[v]);
}
}
int main()
{
in(n),in(m);
for(int i=;i<=n;i++) in(yi[i]);
for(int i=;i<=n;i++) in(hi[i]);
int u,v;
for(int i=;i<=n;i++)
{
in(u),v=i;
if(u!=)
{
E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
}
Edge[i].u=u,Edge[i].v=v;
}
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i);
num=n,cnt=;
memset(head,,sizeof(head));
for(int i=;i<=num;i++)
if(bel[Edge[i].u]!=bel[Edge[i].v])
{
if(Edge[i].u!=)
{
E[++cnt]=head[bel[Edge[i].u]];
V[cnt]=bel[Edge[i].v];
head[bel[Edge[i].u]]=cnt;
vis[bel[Edge[i].v]]=true;
}
else
{
E[++cnt]=head[n+];
V[cnt]=bel[Edge[i].v];
vis[bel[Edge[i].v]]=true;
head[n+]=cnt;
}
}
for(int i=;i<=col;i++)
if(!vis[i])
{
E[++cnt]=head[n+];
V[cnt]=i;
head[n+]=cnt;
}
dfs(n+,m);
cout<<dp[n+][m];
fclose(stdin),fclose(stdout);
return ;
}
T2 codevs 3305 水果姐逛水果街Ⅱ
http://codevs.cn/problem/3305/
树链剖分维护前面减后面的最大值，后面减前面的最大值
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define lson k<<1
#define rson k<<1|1
using namespace std;
const int N=;
int front[N],to[N<<],nxt[N<<],tot,dfn[N],id[N],a[N];
int ls[N<<],rs[N<<],mi[N<<],mx[N<<];
int n,siz[N],dep[N],bl[N],fa[N];
struct node
{
int x,y,z;
};
inline void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-'' ; c=getchar(); }
}
void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
}
void dfs1(int x,int f)
{
siz[x]=;
for(int i=front[x];i;i=nxt[i])
if(to[i]!=f)
{
dep[to[i]]=dep[x]+;
fa[to[i]]=x;
dfs1(to[i],x);
siz[x]+=siz[to[i]];
}
}
void dfs2(int x,int top)
{
bl[x]=top;
dfn[x]=++tot;
id[tot]=x;
int y=;
for(int i=front[x];i;i=nxt[i])
if(to[i]!=fa[x] && siz[to[i]]>siz[y]) y=to[i];
if(!y) return;
dfs2(y,top);
for(int i=front[x];i;i=nxt[i])
if(to[i]!=fa[x] && to[i]!=y) dfs2(to[i],to[i]);
}
inline void up(int k)
{
mi[k]=min(mi[lson],mi[rson]);
mx[k]=max(mx[lson],mx[rson]);
ls[k]=max(mx[rson]-mi[lson],max(ls[lson],ls[rson]));
rs[k]=max(mx[lson]-mi[rson],max(rs[lson],rs[rson]));
}
void build(int k,int l,int r)
{
if(l==r)
{
mi[k]=mx[k]=a[id[l]];
return;
}
int mid=l+r>>;
build(lson,l,mid);
build(rson,mid+,r);
up(k);
}
int getlca(int u,int v)
{
while(bl[u]!=bl[v])
{
if(dep[bl[u]]<dep[bl[v]]) swap(u,v);
u=fa[bl[u]];
}
return dep[u]>dep[v] ? v : u;
}
node qleft(int k,int l,int r,int opl,int opr)
{
if(l>=opl && r<=opr) return (node){mi[k],mx[k],ls[k]};
int mid=l+r>>;
if(opr<=mid) return qleft(lson,l,mid,opl,opr);
if(opl>mid) return qleft(rson,mid+,r,opl,opr);
node lch=qleft(lson,l,mid,opl,opr),rch=qleft(rson,mid+,r,opl,opr);
return (node){min(lch.x,rch.x),max(lch.y,rch.y),max(rch.y-lch.x,max(lch.z,rch.z))};
}
node fleft(int x,int y)
{
if(bl[x]==bl[y]) return qleft(,,n,dfn[y],dfn[x]);
node lch,rch=qleft(,,n,dfn[bl[x]],dfn[x]);
x=fa[bl[x]];
//if(id[bl[x]]<id[bl[y]]) swap(x,y);
while(bl[x]!=bl[y])
{
lch=qleft(,,n,dfn[bl[x]],dfn[x]);
rch.z=max(rch.y-lch.x,max(lch.z,rch.z));
rch.x=min(lch.x,rch.x),rch.y=max(lch.y,rch.y);
x=fa[bl[x]];
}
lch=qleft(,,n,dfn[y],dfn[x]);
rch.z=max(rch.y-lch.x,max(lch.z,rch.z));
rch.x=min(lch.x,rch.x),rch.y=max(lch.y,rch.y);
return rch;
}
node qright(int k,int l,int r,int opl,int opr)
{
if(l>=opl && r<=opr) return (node){mi[k],mx[k],rs[k]};
int mid=l+r>>;
if(opr<=mid) return qright(lson,l,mid,opl,opr);
if(opl>mid) return qright(rson,mid+,r,opl,opr);
node lch=qright(lson,l,mid,opl,opr),rch=qright(rson,mid+,r,opl,opr);
return (node){ min(lch.x,rch.x),max(lch.y,rch.y),max(lch.y-rch.x,max(lch.z,rch.z))};
}
node fright(int x,int y)
{
if(bl[x]==bl[y]) return qright(,,n,dfn[y],dfn[x]);
node rch=qright(,,n,dfn[bl[x]],dfn[x]),lch;
x=fa[bl[x]];
// if(id[bl[x]]<id[bl[y]]) swap(x,y);
while(bl[x]!=bl[y])
{
lch=qright(,,n,dfn[bl[x]],dfn[x]);
rch.z=max(lch.y-rch.x,max(lch.z,rch.z));
rch.x=min(lch.x,rch.x),rch.y=max(lch.y,rch.y);
x=fa[bl[x]];
}
lch=qright(,,n,dfn[y],dfn[x]);
rch.z=max(lch.y-rch.x,max(lch.z,rch.z));
rch.x=min(lch.x,rch.x),rch.y=max(lch.y,rch.y);
return rch;
}
int main()
{
memset(mi,/,sizeof(mi));
int m,u,v,lca;
read(n);
for(int i=;i<=n;i++) read(a[i]);
for(int i=;i<n;i++) read(u),read(v),add(u,v);
dfs1(,);
tot=;
dfs2(,);
build(,,n);
read(m);
while(m--)
{
read(u),read(v);
lca=getlca(u,v);
if(u==lca) printf("%d\n",fleft(v,lca).z);
else if(v==lca) printf("%d\n",fright(u,lca).z);
else
{
node lch=fleft(v,lca),rch=fright(u,lca);
printf("%d\n",max(lch.y-rch.x,max(lch.z,rch.z)));
}
}
return ;
}
T3 hdu 1798 50 years, 50 colors
http://acm.hdu.edu.cn/showproblem.php?pid=1498
枚举颜色
如果（x，y）有气球，则由x向y连边
然后二分图最小点覆盖=最大匹配数
#include<cstdio>
#include<cstring>
using namespace std;
int a[][];
bool v[],vv[];
int match[];
int tot,front[],to[],nxt[];
int ans[];
void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
}
bool dfs(int u)
{
for(int i=front[u];i;i=nxt[i])
if(!v[to[i]])
{
v[to[i]]=true;
if(!match[to[i]] || dfs(match[to[i]]))
{
match[to[i]]=u;
return true;
}
}
return false;
}
int main()
{
//freopen("T3.in","r",stdin);
//freopen("T3.out","w",stdout);
int n,k,res;
bool ok;
while(scanf("%d%d",&n,&k))
{
if(!n) return ;
memset(vv,false,sizeof(vv));
ok=false;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&a[i][j]),vv[a[i][j]]=true;
ans[]=;
for(int i=;i<=;i++)
if(vv[i])
{
tot=;
memset(front,,sizeof(*front)*(n+));
res=;
for(int j=;j<=n;j++)
for(int k=;k<=n;k++)
if(a[j][k]==i) add(j,k);
memset(match,,sizeof(*match)*(n+));
for(int j=;j<=n;j++)
{
memset(v,false,sizeof(*v)*(n+));
if(dfs(j)) res++;
}
if(res>k) ans[++ans[]]=i;
}
if(!ans[]) printf("-1");
else
{
for(int i=;i<ans[];i++) printf("%d ",ans[i]);
printf("%d",ans[ans[]]);
}
printf("\n");
}
}
