首页 > 代码库 > BZOJ1040: [ZJOI2008]骑士
BZOJ1040: [ZJOI2008]骑士
1040: [ZJOI2008]骑士
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1788 Solved: 707
[Submit][Status]
Description
Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
Input
第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
Output
应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
Sample Input
10 2
20 3
30 1
Sample Output
HINT
对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
Source
题解：
终于填了这个巨坑。。。
原来看了好几份题解都不会，现在看起来好simple。。。
貌似这题比创世纪简单？
此题与创世纪的图的形态是一样的，转移的时候设f[x]表选x得到的最大收益，g[x]表不选x得到的最大收益
则：
f[x]=sigma(g[y])
g[x]=sigma(max(f[y],g[y]))
y憎恨x
有了环怎么办？
我们只要随便选一个环上的点x，设x憎恨y
则强制选x，则设立y的f[y]=-inf,因为y不可能被选到了，以x为root dp一次
然后不选x，则y随意，再以x为root dp一次
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 1000000+100014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,rt,ban,a[maxn],fa[maxn],head[maxn];32 ll ans,f[maxn],g[maxn],w[maxn];33 bool v[maxn];34 struct edge{int go,next;}e[maxn];35 inline void dfs(int x)36 {37 v[x]=1;38 if(v[a[x]])rt=x;else dfs(a[x]);39 }40 inline void dp(int x)41 {42 f[x]=w[x];g[x]=0;v[x]=1;43 if(x==ban)f[x]=-inf;44 for(int i=head[x];i;i=e[i].next)45 if(i!=rt&&e[i].go!=fa[x])46 {47 int y=e[i].go;48 fa[y]=x;49 dp(y);50 f[x]+=g[y];51 g[x]+=max(f[y],g[y]);52 }53 }54 int main()55 {56 freopen("input.txt","r",stdin);57 freopen("output.txt","w",stdout);58 n=read();int x;59 for1(i,n)e[i].go=i,w[i]=read(),a[i]=x=read(),e[i].next=head[x],head[x]=i;60 for1(i,n)61 if(!v[i])62 {63 dfs(i);64 ban=a[rt];65 dp(rt);66 ll tmp=f[rt];67 ban=0;68 dp(rt);69 tmp=max(tmp,g[rt]);70 ans+=tmp;71 }72 printf("%lld\n",ans); 73 return 0;74 }
BZOJ1040: [ZJOI2008]骑士