首页 > 代码库 > bzoj1124[POI2008]枪战maf tarjan+树规+贪心/线性DP
bzoj1124[POI2008]枪战maf tarjan+树规+贪心/线性DP
这代码快写死我了.....死人最多随便推推结论。死人最少，每个环可以单独考虑，每个环上挂着的每棵树也可以分别考虑.tarjan找出所有环，对环上每个点，求出选它和不选它时以它为根的树的最大独立集（就是最多活下来的人数），然后环上每个点选或不选对应的是一个“价值”，这个价值是那个点挂着的树里最多存活人数。先全都不选环上的点,算出选和不选时最大独立集的差值，问题变成有一个环，环上有一堆数（那些差值），选出一些不相邻的数使得和最大，然后我按着bzoj2151种树写了个贪心....这个贪心的思路也很神,网上有很多题解.后来发现这个东西和“种树”还不一样，因为种树限制必须种m棵，这个选的个数不限，所以可以O（nlogn）降到O（n），不过这两种方法都能过。另外tarjan不加inline会RE.总之这个方法不太具备可写性.
#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;}
bzoj1124[POI2008]枪战maf tarjan+树规+贪心/线性DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。