【bzoj 1086】王室連邦dfs
1816 ワード
問題が全くできない様子を見る.どうして<=3 bなの?この3は何の役に立ちますか.nは1000しか動的に計画できないのではないでしょうか.例えば、f[i][x]はiをルートiとし、サイズxのブロックにあることを示していますか.しかし、転移方程式は複雑なようで、リュックサックのようなものであるべきだ.肝心なのは分類方法を出力することです.これはどうやって出力しますか.のそこで思い切って問題を解いた.予想外の理にかなっている.一度dfsでいいです.xをルートノードとする場合,その息子sは,サブツリーsにおけるsに接続されたノードの連通ブロックであり,1つの省を構成するには,sを省都としてもxを省都としてもよい.sを省都とすると、sの子樹コードはやはり簡単で、以下のように(コードに無解がないことに気づいたら、b<=nなので明らかに解があるでしょう):
by lych
2015.12.1
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 2005
using namespace std;
int n,m,tot,tp,cnt,fst[N],pnt[N],nxt[N],stk[N],a[N],c[N];
void add(int aa,int bb){
pnt[++tot]=bb; nxt[tot]=fst[aa]; fst[aa]=tot;
}
void dfs(int x,int fa){
int p,last=tp;
for (p=fst[x]; p; p=nxt[p]){
int y=pnt[p]; if (y==fa) continue;
dfs(y,x);
if (tp-last>=m){
c[++cnt]=x;
while (tp>last) a[stk[tp--]]=cnt;
}
}
stk[++tp]=x;
}
int main(){
scanf("%d%d",&n,&m); int i;
for (i=1; i<n; i++){
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0); while (tp) a[stk[tp--]]=cnt;
printf("%d
",cnt);
for (i=1; i<n; i++) printf("%d ",a[i]); printf("%d
",a[n]);
for (i=1; i<cnt; i++) printf("%d ",c[i]); printf("%d
",c[cnt]);
}by lych
2015.12.1