[ZJOI2008]骑士
Time Limit: 10 Sec Memory Limit: 162 MBDescription
Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各
界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。Input
第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力
和他最痛恨的骑士。Output
应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
Sample Input
3 10 2 20 3 30 1
Sample Output
30
HINT
N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
首先有向边改成无向边，因为a痛恨b，就算b不痛恨a，a、b也不能一起选出
其次n个点n条边，一定有一个环，而且是有且只有一个环
据说这个叫环套树，没有标准定义，大概就是一个环，然后环中有节点还连接着树
通俗点儿就是一个连通块，连通块内有且只有一个环
这里是环套树森林，因为不能保证图连通
碰到环一般都断环为链
dfs每一个连通块，找到环，随便找一条边断掉，然后树形DP
怎么DP？
记录下断掉的边的左右端点x，y
做两遍树形DP，第一次不选x，第二次不选y
取大的累加即可
一个错误：
dfs函数中找到一条要断掉的边后，加了reutrn
想加return是因为随便找一条边断掉，既然找到了返回就行，错，原因有2
1、递归，就算reutrn也不能一次回到主函数 2、（主要原因）dfs除了找断掉的边，还有v数组，标记连通块内节点是否被遍历过,目的是使同一连通块内只DP1轮如果加了return，看图说话
#include#include #define N 1000010using namespace std;int tot,to[N*2],next[N*2],front[N],b[N*2];//b数组：标记边的编号，因为加了2条有向边相当于一条无向边，dp过程中防止走断掉的边 int v[N],root,tmp,node,n;bool ok;long long f[N][2],w[N];long long ans,k;void add(int u,int v,int t){ to[++tot]=v;next[tot]=front[u];front[u]=tot;b[tot]=t; to[++tot]=u;next[tot]=front[v];front[v]=tot;b[tot]=t;}void dfs(int x,int fa){ v[x]=1; for(int i=front[x];i;i=next[i]) { int t=to[i]; if(t==fa) continue; if(v[t]) { root=t; node=x; tmp=b[i]; //这里不能加return； } else dfs(t,x); }}void dp(int x,int fa){ f[x][0]=0;f[x][1]=w[x]; for(int i=front[x];i;i=next[i]) { int t=to[i]; if(b[i]==tmp||t==fa) continue; dp(t,x); f[x][0]+=max(f[t][0],f[t][1]); f[x][1]+=f[t][0]; }}int main(){ scanf("%d",&n); int x; for(int i=1;i<=n;i++) { scanf("%lld%d",&w[i],&x); add(i,x,i); } for(int i=1;i<=n;i++) { if(!v[i]) { dfs(i,0); dp(root,0); k=f[root][0]; dp(node,0); k=max(k,f[node][0]); ans+=k; } } printf("%lld",ans);}
粘一个每个连通块只DP一次的代码
时间消耗是上面的一半
然而看不懂。。。
#include#include #define N 1000001using namespace std;queue q;int n,w[N],son[N],in[N],v[N],root[N],cnt,bak[N];long long f[N][4],ans;void dfs(int x){ v[x]=x;int i; for(i=son[x];!v[i];i=son[i]) v[i]=x; if(v[i]==x) { root[++cnt]=i;bak[son[i]]=1; --in[son[i]];son[i]=0; }}void treedp(){ int x,y; for(int i=1;i<=n;i++) { f[i][1]=w[i]; if(!bak[i]) f[i][3]=w[i]; } for(int i=1;i<=n;i++) if(!in[i]) q.push(i); while(!q.empty()) { x=q.front();q.pop(); y=son[x]; if(!y) continue; f[y][0]+=max(f[x][1],f[x][0]); f[y][1]+=f[x][0]; f[y][2]+=max(f[x][2],f[x][3]); if(!bak[y]) f[y][3]+=f[x][2]; --in[y]; if(!in[y]) q.push(y); }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&w[i],&son[i]); in[son[i]]++; } for(int i=1;i<=n;i++) if(!v[i]) dfs(i); treedp(); for(int i=1;i<=cnt;i++) ans+=max(f[root[i]][0],f[root[i]][3]); printf("%lld\n",ans);}