ZJOI2008 骑士
枫林晚
2018-05-15 17:12:07
## 题目大意：
N个骑士组个队，每个骑士有战力，每个骑士恨一人，相互憎恨不同在队里，怎样安排战斗力最大？输出最大总战斗力即可。
## 分析：
明显的，每个骑士恨一个人，那么这两个人之间可以连一条边。是有向的还是无向的？可以想到，如果一个骑士恨一个骑士，那么他们两个无论如何不可能在这个队里，我恨你，就相当于你恨我，所以要连接一条无向边。
所以这样我们得到了一个森林，森林里的每一棵树，要么是一棵普通的树，要么是一个带环的图，因为每个骑士只最恨一个人，不难证明，这个图一定只有一个环。所以就是环套树。
## 做法：
1.输入建边。
2.不断dfs找到所有的树或者是环套树。
3每个dfs后，处理每一棵树。
4.处理的时候，f[i][0/1],表示在i所在的子树中，0代表这个骑士不选，1代表选所可以获得的最大的战斗力。如果是树，直接树形dp；
如果环套树，拆环成链，从环上任意一个地方断开，断点设为r1,r2，以r1为根树形dp一遍，并强制让r1不能被选，即为f[r1][0];同理，r2也这样一下，记录f[r2][0],这样相当于，在强制r1/r2中选一个或者都不选的情况下，进行一个树形dp。
ans加上这两次dp的最大值即可。
详见代码（极丑，但是易懂）：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000000+10;
int p[N];//战斗力
struct node{
int to,nxt;
}bian[2*N];
int head[N],cnt=1;//邻接表
int mem[N];//每个树的元素 mem[0]用来计数
bool vis[N];//元素是否访问过
bool flag;//该次dfs找到的树是不是有环
int r1,r2;//有环的话，第一次找到环的位置作为断点
ll ans;
ll f[N][2];//dp数组 i为子树，i选或不选战斗力总和最大值
void add(int x,int y)
{
bian[++cnt].nxt=head[x];
bian[cnt].to=y;
head[x]=cnt;
}
void dfs(int x,int fa)
{
vis[x]=1;
mem[++mem[0]]=x;
for(int i=head[x];i;i=bian[i].nxt)
{
int y=bian[i].to;
if(y==fa) continue;
if(!vis[y]) dfs(y,x);
else if(vis[y]&&!flag)
{
flag=true;//find circle!!
r1=x,r2=y;
}
}
}//dfs 找到一棵新树。
void dfs2(int x,int fa)
{
f[x][0]=0;
f[x][1]=p[x];
for(int i=head[x];i;i=bian[i].nxt)
{
int y=bian[i].to;
if(y&&y!=fa)
{
dfs2(y,x);
f[x][1]+=f[y][0];
f[x][0]+=max(f[y][0],f[y][1]);
}
}
}//dfs2 树形dp
void clear()
{
mem[0]=0;
flag=false;
}//清空
void work()
{
if(!flag)//是棵树
{
int root=mem[1];
dfs2(root,-1);
ans+=max(f[root][0],f[root][1]);
}
else//是环套树
{
ll mx=-100;
for(int i=head[r1];i;i=bian[i].nxt)
{
if(bian[i].to==r2)
{
bian[i].to=0;
bian[i^1].to=0;
break;
}
}
dfs2(r1,-1);
mx=max(mx,f[r1][0]);
dfs2(r2,-1);
mx=max(mx,f[r2][0]);
ans+=mx;
}
}
int n;
int main()
{
scanf("%d",&n);
int x,y;
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i],&x),add(i,x),add(x,i);
for(int i=1;i<=n;i++)
{
if(!vis[i])//每次找到一个!vis[i], 就一定有一棵树。
{
clear();
dfs(i,-1);
work();
}
}
printf("%lld",ans);
return 0;
}
```