这代码快写死我了.....死人最多随便推推结论。死人最少，每个环可以单独考虑，每个环上挂着的每棵树也可以分别考虑.tarjan找出所有环，对环上每个点，求出选它和不选它时以它为根的树的最大独立集（就是最多活下来的人数），然后环上每个点选或不选对应的是一个“价值”，这个价值是那个点挂着的树里最多存活人数。先全都不选环上的点,算出选和不选时最大独立集的差值，问题变成有一个环，环上有一堆数（那些差值），选出一些不相邻的数使得和最大，然后我按着bzoj2151种树写了个贪心....这个贪心的思路也很神,网上有很多题解.后来发现这个东西和“种树”还不一样，因为种树限制必须种m棵，这个选的个数不限，所以可以O（nlogn）降到O（n），不过这两种方法都能过。另外tarjan不加inline会RE.总之这个方法不太具备可写性.
UPD:现在发现我当时是把这题写成bzoj1040了，囧。
#include<cstdio> #include<queue> #include<vector> using namespace std; const int maxn=1500005; int aim[maxn]; struct edge{//反向建边 int to,next; }lst[maxn],lst2[maxn];int len=1,len2=1; int first[maxn],first2[maxn]; void addedge(int a,int b){ lst[len].to=b; lst[len].next=first[a]; first[a]=len++; } void addedge2(int a,int b){ lst2[len2].to=b; lst2[len2].next=first2[a]; first2[a]=len2++; } int T; int s[maxn],low[maxn],dfn[maxn],indeg[maxn],top; int belong[maxn],sz[maxn],cnt; bool ins[maxn]; inline void tarjan(int x){ dfn[x]=low[x]=++T; s[top++]=x;ins[x]=true; if(!dfn[aim[x]]){ tarjan(aim[x]); if(low[aim[x]]<low[x])low[x]=low[aim[x]]; }else if(ins[aim[x]]&&dfn[aim[x]]<low[x])low[x]=dfn[aim[x]]; if(low[x]==dfn[x]){ ++cnt; do{ ins[s[--top]]=false; belong[s[top]]=cnt; sz[cnt]++; addedge2(cnt,s[top]); }while(s[top]!=x); } } bool die[maxn]; int f[2][maxn];//bool vis[2][maxn];//f[][]求活人数目 int max(int a,int b){ return a>b?a:b; } int q[maxn];bool vis[maxn]; void dp(int s){ int head=0,tail=0; if(vis[s])return; q[tail++]=s; while(head!=tail){ int x=q[head++];vis[x]=true; for(int pt=first[x];pt;pt=lst[pt].next){ if(!vis[lst[pt].to])q[tail++]=lst[pt].to; } } for(int i=tail-1;i>=0;--i){ int x=q[i]; f[1][x]=1; for(int pt=first[x];pt;pt=lst[pt].next){ if(belong[lst[pt].to]==belong[x])continue; f[1][x]+=f[0][lst[pt].to]; if(die[lst[pt].to])f[0][x]+=f[0][lst[pt].to]; else f[0][x]+=max(f[0][lst[pt].to],f[1][lst[pt].to]); } } } int w[maxn];/* int work(int num){//第num个SCC最多生还多少人。种树？？？ ++T; priority_queue<node> q; int ans=0;//猜测SCC节点出栈是按照在环上的顺序 for(int i=1;i<=sz[num];++i){ nxt[i]=i+1; pre[i]=i-1; } nxt[sz[num]]=1;pre[1]=sz[num]; int j=0; for(int pt=first2[num];pt;pt=lst2[pt].next){ ans+=f[0][lst2[pt].to]; if(!die[lst2[pt].to])w[++j]=f[1][lst2[pt].to]-f[0][lst2[pt].to]; else w[++j]=0; q.push(node(j)); }//for(int i=1;i<=j;++i)printf("%d ",w[i]);printf("\n"); while(!q.empty()){//最后一次拿出来的时候会出错吗？ node tmp=q.top();q.pop(); if(used[tmp.k]==T)continue; if(w[tmp.k]<=0)break; ans+=w[tmp.k];//printf("%d %d\n",tmp.k,w[tmp.k]); w[tmp.k]=w[pre[tmp.k]]+w[nxt[tmp.k]]-w[tmp.k];//printf("w%d\n",w[tmp.k]); used[pre[tmp.k]]=used[nxt[tmp.k]]=T; if(pre[tmp.k]==nxt[tmp.k])break; pre[tmp.k]=pre[pre[tmp.k]];nxt[tmp.k]=nxt[nxt[tmp.k]]; if(used[pre[tmp.k]]==T||used[nxt[tmp.k]]==T)break; pre[nxt[tmp.k]]=tmp.k;nxt[pre[tmp.k]]=tmp.k;// printf("%d %d %d %d\n",w[1],w[2],w[3],w[4]); q.push(node(tmp.k)); }//printf("%d\n",ans); return ans; }*/ int F[2][2][maxn]; int work(int num){ int j=0,ans=0; for(int pt=first2[num];pt;pt=lst2[pt].next){ ans+=f[0][lst2[pt].to]; if(!die[lst2[pt].to])w[++j]=f[1][lst2[pt].to]-f[0][lst2[pt].to]; else w[++j]=0; } F[1][1][1]=w[1];F[0][0][1]=0;F[0][1][1]=F[1][0][1]=-0x3f3f3f3f; for(int i=2;i<=j;++i){ F[0][1][i]=F[0][0][i-1]+w[i]; F[1][1][i]=F[1][0][i-1]+w[i]; F[0][0][i]=max(F[0][0][i-1],F[0][1][i-1]); F[1][0][i]=max(F[1][0][i-1],F[1][1][i-1]); } return ans+max(F[0][0][j],max(F[0][1][j],F[1][0][j])); } int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",aim+i); //if(i==aim[i])die[i]=true; //else addedge(aim[i],i); } for(int i=1;i<=n;++i){ if(!dfn[i])tarjan(i); } for(int i=1;i<=n;++i){ if(belong[i]!=belong[aim[i]])indeg[belong[aim[i]]]++; if(i==aim[i])indeg[belong[i]]++; } for(int i=1;i<=n;++i){ if(!first[i]){ die[aim[i]]=true; } } for(int i=1;i<=n;++i){ dp(i); } int ans1=n; for(int i=1;i<=n;++i){ if(aim[i]==i){ ans1-=f[0][i]; } } for(int i=1;i<=cnt;++i){ if(sz[i]>1){ ans1-=work(i); } } int ans2=n; for(int i=1;i<=cnt;++i){ if(!indeg[i])ans2--; } printf("%d %d\n",ans1,ans2); return 0; }
转载于:https://www.cnblogs.com/liu-runda/p/5940191.html
相关资源：数据结构—成绩单生成器