「BZOJ1040」[ZJOI2008] 骑士 2014年2月26日5,2840 Description Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。 Input 第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。 Output 应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。 Sample Input 3 10 2 20 3 30 1 Sample Output 30 「数据规模」 对于30%的测试数据，满足N ≤ 10； 对于60%的测试数据，满足N ≤ 100； 对于80%的测试数据，满足N ≤ 10 000。 对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
wa:
#include<cstdio> #include<cstring> #define LL long long using namespace std; const int maxn=1e6+5; inline LL max(LL a,LL b){ return (a<b?b:a); } int first[maxn],next[maxn*2],to[maxn*2]; int edge_count=0; inline void add(int x,int y){ edge_count++; to[edge_count]=y; next[edge_count]=first[x]; first[x]=edge_count; } int n,a[maxn],fa[maxn]; inline void read(int &a){ a=0;char x=getchar(); while(x<‘0‘ || ‘9‘<x){ x=getchar(); } while(‘0‘<=x && x<=‘9‘){ a=(a<<3)+(a<<1)+x-‘0‘; x=getchar(); } } bool vis[maxn]={0}; int x[maxn],y[maxn],p=1; void dfs(int root,int fa){ if(x[p] && y[p])return; vis[root]=1; for(register int i=first[root];i;i=next[i]){ if(to[i]==fa)continue; if(vis [ to[i] ]){ x[p]=root; y[p]=to[i]; return; } dfs(to[i],root); } } LL f[maxn][2],ans=0ll; //1->选了 0->没选 void search(int root){ vis[root]=1; f[root][1]=a[root]; for(register int i=first[root];i;i=next[i]){ if( vis[ to[i] ] )continue; search(to[i]); f[root][1]+=f[ to[i] ][0]; f[root][0]+=max(f[ to[i] ][1],f[ to[i] ][0]); } } int main() { //freopen("knight.in","r",stdin); scanf("%d",&n); for(register int i=1;i<=n;i++){ read(a[i]);read(fa[i]); add(i,fa[i]); add(fa[i],i); } for(register int i=1;i<=n;i++){ if(!vis[i]){ dfs(i,0); //printf("%d %d\n",x[p],y[p]); p++; } } for(int i=1;i<p;i++){ LL temp=0ll; memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); search(x[i]); temp=f[ x[i] ][0]; memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); search(y[i]); temp=max(temp,f[ y[i] ][0]); ans+=temp; } printf("%lld",ans); return 0; }
std
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #define N 1000001 #define ll long long using namespace std; int n,cnt;ll ans,answer; int v[N],fa[N],head[N],to[N],next[N],ez[N],bh[N]; ll dp[N][2],f[N][4]; bool mark[N]; void Ins(int a,int b) {cnt++;to[cnt]=b;next[cnt]=head[a];head[a]=cnt;} void init() { int i,k; scanf("%d",&n); for(i=1;i<=n;i++) {scanf("%d%d",&v[i],&k);Ins(k,i);fa[i]=k;} } void treedp(int x) { dp[x][1]=v[x];dp[x][0]=0; mark[x]=1; int i=head[x]; while(i>0) { treedp(to[i]); dp[x][0]+=max(dp[to[i]][0],dp[to[i]][1]); dp[x][1]+=dp[to[i]][0]; i=next[i]; } } void finaldp() { int i,k; ans=0; f[1][1]=0;f[1][2]=0; f[1][0]=dp[bh[1]][1]; f[1][3]=dp[bh[1]][0]; for(i=2;i<=bh[0];i++) { k=bh[i]; f[i][0]=f[i-1][1]+dp[k][1]; f[i][1]=max(f[i-1][0],f[i-1][1])+dp[k][0]; f[i][2]=f[i-1][3]+dp[k][1]; f[i][3]=max(f[i-1][2],f[i-1][3])+dp[k][0]; } ans=max(f[bh[0]][1],max(f[bh[0]][2],f[bh[0]][3])); } void solve() { int i,k,j,now; for(i=1;i<=n;i++) { if(mark[i])continue; bh[0]=0; k=i; while(!mark[k]) { mark[k]=1; k=fa[k]; ez[fa[k]]=k; } now=k; while(1) { i=head[k]; dp[k][1]=v[k]; while(i>0) { if(to[i]!=ez[k]) {treedp(to[i]); dp[k][0]+=max(dp[to[i]][0],dp[to[i]][1]); dp[k][1]+=dp[to[i]][0];} i=next[i]; } bh[0]++;bh[bh[0]]=k; k=fa[k]; if(k==now) break; } finaldp(); answer+=ans; } printf("%lld",answer); } int main() { init(); solve(); return 0; }
原文：https://www.cnblogs.com/a-blog-of-taojiayi-2003/p/10692334.html