| 记录编号 |
318842 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
膜法师 |
最终得分 |
100 |
| 用户昵称 |
 liu_runda |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
2.110 s |
| 提交时间 |
2016-10-09 21:38:07 |
内存使用 |
83.28 MiB |
显示代码纯文本
/*
分析问题：将“膜与被膜”的关系建成边，我们可以认为第一问是图上的最大独立集问题。
其中，要求有自环的人必须被选中，不被膜的人必须被选中.
这个图是一堆环，每个环上长了一堆树，所以我们对环上的每棵树跑树上最大独立集，再在环上跑一个线性DP...
第二问自己推推结论。
*/
#include<cstdio>
#include<cassert>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
char ch;
void read(int &x){
while(ch=getchar(),!isdigit(ch));
x=ch-'0';
while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
}
const int maxn=1000005;
struct edge{
int to,next;
}lst[maxn];int len=1;
int first[maxn];
void addedge(int a,int b){
lst[len].to=b;
lst[len].next=first[a];
first[a]=len++;
}
int to[maxn];
int T;
int dfn[maxn],low[maxn],s[maxn],top,belong[maxn],cnt,indeg[maxn],sz[maxn];
bool ins[maxn];
vector<int> scc[maxn];
inline void tarjan(int x){
dfn[x]=low[x]=++T;
s[top++]=x;ins[x]=true;
for(int pt=first[x];pt;pt=lst[pt].next){
if(!dfn[lst[pt].to]){
tarjan(lst[pt].to);
if(low[lst[pt].to]<low[x])low[x]=low[lst[pt].to];
}else if(ins[lst[pt].to]&&dfn[lst[pt].to]<low[x])low[x]=dfn[lst[pt].to];
}
if(low[x]==dfn[x]){
++cnt;
do{
ins[s[--top]]=false;
belong[s[top]]=cnt;
sz[cnt]++;
scc[cnt].push_back(s[top]);
}while(s[top]!=x);
}
}
bool not_mo[maxn];
bool dpdone[maxn];
int f[2][maxn];//f[0][i]:不选择i时,以i为根的子树的最大独立集 f[1][i]:选择i. "选择某个点"对应”这个人直到最后也不被膜“
int q[maxn];int head,tail;
int max(int a,int b){
return a>b?a:b;
}
void treedp(int x){//非递归式树规，先求出bfs序再按bfs序倒序处理
head=tail=0;
q[tail++]=x;
while(head!=tail){
x=q[head++];dpdone[x]=true;
for(int pt=first[x];pt;pt=lst[pt].next){
if(belong[x]==belong[lst[pt].to])continue;
if(!dpdone[lst[pt].to]){
q[tail++]=lst[pt].to;
}
}
}
for(int i=tail-1;i>=0;--i){
x=q[i];
if(not_mo[x]){//最后必然不会被膜，因此只有f[1][x],没有f[0][x],f[0][x]设为-inf
f[0][x]=-0x7f7f7f7f;
f[1][x]=1;
continue;
}
f[1][x]=1;
bool flag=false;
for(int pt=first[x];pt;pt=lst[pt].next){
if(belong[x]==belong[lst[pt].to])continue;
if(not_mo[lst[pt].to]){//发现一个必然不会被膜的人要膜x,那么x必然会被膜，只有f[0][x],没有f[1][x]
flag=true;
}
f[1][x]+=f[0][lst[pt].to];
f[0][x]+=max(f[0][lst[pt].to],f[1][lst[pt].to]);
}
if(flag)f[1][x]=-0x7f7f7f7f;//这个f[1][x]如果被用到，一定会先和f[0][x]取较大值，因此不会相加溢出
}
}
int delta[maxn];
int g[2][2][maxn];//第一维：开头的数是否选择 第二维:当前处理的数是否选择(对于f[][][i]就是第i个数)
int lineardp(int sccnum){//编号为sccnum的环上最多能有多少人不被膜
int ans=0,lim=sz[sccnum];
for(int i=0;i<lim;++i){
ans+=f[0][scc[sccnum][i]];
if(f[1][scc[sccnum][i]]<0)delta[i]=0;
else delta[i]=f[1][scc[sccnum][i]]-f[0][scc[sccnum][i]];//环上每个位置可以选f[0]或f[1],相邻位置不能同时选f[1],我们先全都选f[0]
//把i从f[0]换成f[1]k可以得到delta[i],环上两个相邻的delta[i]不能同时得到,接下来用线性dp可以求出最大可获得的delta[i]之和
}
g[0][0][0]=0;g[1][1][0]=delta[0];g[1][0][0]=-0x3f3f3f3f;g[0][1][0]=-0x3f3f3f3f;
for(int i=1;i<lim;++i){
g[0][0][i]=max(g[0][1][i-1],g[0][0][i-1]);
g[1][0][i]=max(g[1][1][i-1],g[1][0][i-1]);
g[0][1][i]=g[0][0][i-1]+delta[i];
g[1][1][i]=g[1][0][i-1]+delta[i];
}//f[1][1][sz[sccnum]-1]为非法状态
return ans+max(g[0][0][lim-1],max(g[0][1][lim-1],g[1][0][lim-1]));//一定要记得在dp的最佳状态上加上一开始的ans
}
int main(){
freopen("maf.in","r",stdin);
freopen("maf.out","w",stdout);
int __size__=128<<20;
char *__p__=(char*)malloc(__size__)+__size__;
__asm__("movl %0, %%esp\n"::"r"(__p__));
int n;read(n);
int ans1=n,ans2=n;//ans1:被膜的人最少 ans2:被膜的人最多
for(int i=1;i<=n;++i){
read(to[i]);
if(to[i]==i){
continue;
}
addedge(to[i],i);
}
for(int i=1;i<=n;++i){
if(!dfn[i]&&to[i]!=i){
tarjan(i);
}
}
//被膜的人最多，采用总人数-无法被膜的人数。零入度的点无法被膜，每个孤立的环会剩下一个点无法被膜
for(int i=1;i<=n;++i){
if(belong[i]!=belong[to[i]])indeg[belong[to[i]]]++;
}
for(int i=1;i<=cnt;++i){
if(indeg[i]==0)ans2--;//indeg[i]==0:孤立的环/零入度的点，均会剩下一个人
}
for(int i=1;i<=n;++i){
if(sz[belong[i]]==1&&indeg[belong[i]]==0)not_mo[i]=true;
}
for(int i=1;i<=n;++i){
if(!dpdone[i])treedp(i);
}
//for(int i=1;i<=n;++i){
// printf("%d %d\n",f[0][i],f[1][i]);
// }
//ans2:用总人数减去最多的不被膜人数
for(int i=1;i<=n;++i){
if(to[i]==i){
ans1-=f[0][i];
}
}
for(int i=1;i<=cnt;++i){
if(sz[i]>1){
ans1-=lineardp(i);
}
}
printf("%d %d\n",ans1,ans2);//while(1);
fclose(stdin);fclose(stdout);
return 0;
}