Run
题意:
给出一张图(点数为n,边数为m)的一个生成树和一些非树边。
每条非树边有一个代价w,表示炸毁这条边需要付出的代价。
求炸毁一些非树边使得图中不存在偶环所付出的最小代价。
特别地,生成树上点的度数不超过10.
数据范围:n<=1000,m<=4000
分析:
首先如果一条非树边跨越了树上奇数条边,则这条边必须炸毁。
剩下的边,如果任意两条边所跨越的树上路径有公共边,则会存在偶环。
考虑到每个节点的儿子最多只有10个,我们可以考虑状压dp.
令f[x][s]表示以x为根的子树,只考虑集合s中儿子时能保留的边的最大权值。
令g[x][i]表示以x为根的子树,不考虑x的第i个儿子时能保留的边的最大权值。
每条非树边,只在它的端点的lca处考虑影响。
为了让路径不重复,则该非树边所覆盖的路径都不能被选。
暴力从一个端点到lca统计不考虑路径上的边时的最大权值。
再与该非树边没有覆盖的部分一起更新答案。
复杂度O(n*210+n*m)
#include <vector> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define g() getchar() template<class Q>void Scan(Q&x){ char c;int f=1; while(c=g(),c<48||c>57)if(c=='-')f=-1; for(x=0;c>47&&c<58;c=g())x=10*x+c-48; x*=f; } #define Max(x,y) if(x<y)x=y #define Min(x,y) if(x>y)x=y #define pb push_back #define rep(i,a,b) for(int i=a;i<b;++i) const int MAXN=1005; const int MAXS=1<<10; int n,m; struct edge{ int t,n; edge(int t=0,int n=0):t(t),n(n){} }e[MAXN<<1]; int head[MAXN],tot; inline void AddEdge(int s,int t){ e[++tot]=edge(t,head[s]),head[s]=tot; e[++tot]=edge(s,head[t]),head[t]=tot; } int p[MAXN],dep[MAXN]; vector<int>ch[MAXN],qy[MAXN]; void dfs(int x){ for(int i=head[x],y;i;i=e[i].n) if((y=e[i].t)!=p[x]){ p[y]=x; dep[y]=dep[x]+1; ch[x].pb(y); dfs(y); } } inline int lca(int x,int y){ if(dep[x]>dep[y])swap(x,y); while(dep[y]>dep[x])y=p[y]; while(p[x]!=p[y])x=p[x],y=p[y]; return x==y?x:p[x]; } struct edge1{ int u,v,w; inline void scan(){ Scan(u),Scan(v),Scan(w); } }tmp[MAXN*5]; int ans; inline void Init(){ Scan(n),Scan(m); rep(i,1,m+1){ tmp[i].scan(); ans+=tmp[i].w; if(!tmp[i].w){ AddEdge(tmp[i].u,tmp[i].v); } } dfs(1); rep(i,1,m+1){ if(!tmp[i].w)continue; int u=tmp[i].u,v=tmp[i].v; int Lca=lca(u,v); if((dep[u]+dep[v]-dep[Lca]*2)&1)continue; qy[Lca].pb(i); } } int dp[MAXN]; int f[MAXN][MAXS],g[MAXN][10]; inline int swim(int x,int par,int&res){ int ban=-1; while(x!=par){ if(~ban)res+=g[x][ban]; else res+=dp[x]; int s=ch[p[x]].size(); rep(i,0,s) if(x==ch[p[x]][i]){ ban=i; break; } x=p[x]; } return ban; } void tree_dp(int x){ for(int i=head[x],y;i;i=e[i].n) if((y=e[i].t)!=p[x])tree_dp(y); int s=ch[x].size(); int maxs=1<<s; rep(set,0,maxs){ int res=0; rep(i,0,s) if(set>>i&1){ res+=dp[ch[x][i]]; } Max(f[x][set],res); } int c=qy[x].size(); rep(i,0,c){ int u=tmp[qy[x][i]].u; int v=tmp[qy[x][i]].v; int res=tmp[qy[x][i]].w; int bu=max(0,1<<swim(u,x,res)); int bv=max(0,1<<swim(v,x,res)); rep(set,0,maxs){ if(bu&&(set&bu)==bu||bv&&(set&bv)==bv) continue; int ns=set^bu^bv; Max(f[x][ns],res+f[x][set]); } } rep(set,0,maxs){ rep(i,0,s) if(!(set>>i&1)){ Max(g[x][i],f[x][set]); } Max(dp[x],f[x][set]); } } inline void Solve(){ tree_dp(1); ans-=dp[1]; printf("%d\n",ans); } int main(){ freopen("run.in","r",stdin); freopen("run.out","w",stdout); Init(); Solve(); return 0; }
hdu4625 JZPTREE
题意:给出一棵树,边权均视为1,对于树上每一个点u,求∑v dis(u,v)k
我特意去买了本混凝土数学。。。
《具体数学》:xn=∑k S2(n,k)*A(x,k) (S2表示第二类斯特林数,我不会用Latex别D我。。。)
这个公式的正确性显然,把有x个元素的集合划分为k个集合,允许空集的方案数为xn
再做个简单的变换可以得到:xn=∑k S2(n,k)*k!*C(x,k)
则(x+1)n=∑k S2(n,k)*k!*C(x+1,k)
组合数有性质:C(n,k)=C(n-1,k)+C(n-1,k-1)
则(x+1)n=∑k S2(n,k)*k!*(C(x,k)+C(x,k-1))=xn+∑k S2(n,k)*k!*C(n,k-1)
实际上,我们容易发现 S2(n,k)*k! 这个算子一直没有发生改变,所以我们可以预处理出S2(n,k)*k!的值
令dp[x][k]=∑y(y属于以x为根的子树) C(dis(x,y),k)
则dp[x][k]=∑y(y是与x的儿子) dp[y][k]+dp[y][k-1]
先dfs 一次求出以1为根的所有dp值,再dfs一次,使根为当前节点x并计算 ∑k S2(n,k)*k!*dp[x][k]
复杂度:预处理 O(k2)+dp O(nk)
#include <math.h> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define g() getchar() template<class Q>void Scan(Q&x){ char c;int f=1; while(c=g(),c<48||c>57)if(c=='-')f=-1; for(x=0;c>47&&c<58;c=g())x=10*x+c-48; x*=f; } #define rep(i,a,b) for(int i=a;i<b;++i) const int MAXN=50005; const int MAXK=505; const int Mod=10007; struct edge{ int t,n; edge(int t=0,int n=0): t(t),n(n){} }e[MAXN<<1]; int head[MAXN],tot; inline void AddEdge(int s,int t){ e[++tot]=edge(t,head[s]),head[s]=tot; e[++tot]=edge(s,head[t]),head[t]=tot; } int n,k; inline void Init(){ Scan(n),Scan(k); rep(i,1,n+1)head[i]=0; tot=0; rep(i,1,n){ int u,v; Scan(u),Scan(v); AddEdge(u,v); } } int T; int s[MAXK][MAXK],fac[MAXK]; inline void init(){ s[0][0]=fac[0]=1; rep(i,1,MAXK){ fac[i]=fac[i-1]*i%Mod; rep(j,1,MAXK){ s[i][j]=(j*s[i-1][j]+s[i-1][j-1])%Mod; } } rep(i,1,MAXK) rep(j,1,MAXK){ s[i][j]=s[i][j]*fac[j]%Mod; } } int dp[MAXN][MAXK]; void prev_dfs(int x,int p){ dp[x][0]=1; rep(i,1,k+1)dp[x][i]=0; for(int i=head[x],y;i;i=e[i].n) if((y=e[i].t)!=p){ prev_dfs(y,x); rep(j,0,k+1){ dp[x][j]+=dp[y][j]; if(j)dp[x][j]+=dp[y][j-1]; dp[x][j]%=Mod; } } } int ans[MAXN]; void dfs(int x,int p){ ans[x]=0; rep(i,0,k+1) ans[x]=(ans[x]+s[k][i]*dp[x][i])%Mod; for(int i=head[x],y;i;i=e[i].n) if((y=e[i].t)!=p){ rep(j,0,k+1){ dp[x][j]+=Mod-dp[y][j]; if(j)dp[x][j]+=Mod-dp[y][j-1]; dp[x][j]%=Mod; } rep(j,0,k+1){ dp[y][j]+=dp[x][j]; if(j)dp[y][j]+=dp[x][j-1]; dp[y][j]%=Mod; } dfs(y,x); rep(j,0,k+1){ dp[y][j]+=Mod-dp[x][j]; if(j)dp[y][j]+=Mod-dp[x][j-1]; dp[y][j]%=Mod; } rep(j,0,k+1){ dp[x][j]+=dp[y][j]; if(j)dp[x][j]+=dp[y][j-1]; dp[x][j]%=Mod; } } } inline void Solve(){ prev_dfs(1,0); dfs(1,0); rep(i,1,n+1) printf("%d\n",ans[i]); } int main(){ for(init(),Scan(T);T--;Init(),Solve()); return 0; }