[BZOJ]2068: [Poi2004]SZP

题解: 根据题目的特殊性我们考虑基环树对于非树边uv我们对深度较高的点分情况讨论取或者不取然后做个树dp就行了

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=1e6+1100;
const double eps=1e-8;
#define ll long long
using namespace std;
const int inf=1e9;
struct edge{int t;edge*next;}e[MAXN],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

vector<pii>circle;
bool vis[MAXN],c[MAXN];
int n;
int base,Base;
int dp[MAXN][2],dp1[MAXN][2];

void tarjan(int x,int y){
    circle.pb(mp(x,y));
}

void dfs(int x){
    vis[x]=1;
    link(x){
	if(j->t==base)tarjan(x,base);
	else if(!vis[j->t])dfs(j->t);
    }
}

void _dfs(int x){
    bool flag=0,flag1=0;int minn=inf;
    link(x){
	if(j->t==base)continue;
	_dfs(j->t);
	flag1=1;
	dp[x][0]+=max(dp[j->t][0],dp[j->t][1]);
	if(dp[j->t][0]>=dp[j->t][1])flag=1;
	if(j->t!=Base)minn=min(minn,dp[j->t][1]-dp[j->t][0]);
    }
    if(x==Base||flag)dp[x][1]=dp[x][0]+1;
    else dp[x][1]=max(0,dp[x][0]-minn+1);
}

void __dfs(int x){
    bool flag=0,flag1=0;int minn=inf;
    link(x){
	if(j->t==base)continue;
	__dfs(j->t);
	flag1=1;
	dp1[x][0]+=max(dp1[j->t][0],dp1[j->t][1]);
	if(dp1[j->t][0]>=dp1[j->t][1])flag=1;
	minn=min(minn,dp1[j->t][1]-dp1[j->t][0]);
    }
    if(flag)dp1[x][1]=dp1[x][0]+1;
    else dp1[x][1]=dp1[x][0]-minn+1;
}

int main(){
    n=read();
    inc(i,1,n){int x=read();add(x,i);}
    inc(i,1,n)if(!vis[i]){base=i;dfs(i);}
    int ans=0;
    for(int i=0;i<circle.size();i++){
	int x=circle[i].first;int y=circle[i].second;
	base=y;Base=x;
	_dfs(y);__dfs(y);
	ans+=max(dp[y][0],max(dp1[y][1],dp1[y][0]));
    }
    printf("%d
",ans);
}

2068: [Poi2004]SZP

Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 258 Solved: 118
[Submit][Status][Discuss]

Description

Byteotian 中央情报局 (BIA) 雇佣了许多特工. 他们每个人的工作就是监视另一名特工. Byteasar 国王需要进行一次秘密行动,所以他要挑选尽量多的信得过的特工. 但是这项任务是如此的机密以至于所有参加行动的特工都必须至少被另一名没有参加任务的特工所监视( 就是说如果某个特工参加了行动,那么原先监视他的那些特工中至少要有一个没有参加进行动). 给出监视任务的详情,要求计算最多能有多少个特工参与其中.

Input

第一行只有一个整数, n – 特工的总数, 2 <= n <= 1000000. 特工从1 到 n编号. 接下来n行每行一个整数ak 表示特工k将要监视特工ak , 1 <= k <= n, 1 <= ak <= n, ak <> k.

Output

打印一个数,最多能有多少特工参加入这个任务.

Sample Input

6
2
3
1
3
6
5