BZOJ 1124 [POI2008]枪战Maf 贪心+乱搞

题意:略。方法:贪心+乱搞。解析:今天做的题里面最难的了…分连通块进行考虑。一个连通块最多死多少呢？一个点 -> 死一个一个环 -> 死环上点个数-1个一个环加上内向树 -> 死所有点个数-入度为0个。这很显然。。一棵树嘛..倒着开枪..最少死多少个呢？首先入度为零的肯定死不了。然后我们将入度为0的推入队列。之后他打死一个人后看那个人要打的人是否变成了入度为零。如果变成了入度为零那么继续进队。最后整张图剩下了一堆环。环的结论很显然，明显是个数/2。所以答案就出来啦.代码:;int n,cnt;int a[N];int du[N];int head[N];int vis[N];int v[N];int fir[N];struct node{int from,to,next;}edge[N<<1];int belong[N];int cnt_du[N];int siz[N];int tot;void init(){memset(head,-1,sizeof(head));cnt=1;}void edgeadd(int from,int to){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}void dfs(int now,int ff){vis[now]=1,belong[now]=tot,siz[tot]++;for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(to==now||to==ff||vis[to])continue;dfs(to,now);}}int check(int now,int num){v[now]=1;int t=now,cntt=1;while(!v[a[t]]){v[a[t]]=1;t=a[t];cntt++;}t=a[t];if(t==now&&cntt==num)return 1;return 0;}int main(){init();scanf(“%d”,&n);for(int i=1;i<=n;i++){scanf(“%d”,&a[i]);du[a[i]]++;edgeadd(i,a[i]);edgeadd(a[i],i);}for(int i=1;i<=n;i++){if(!vis[i])tot++,dfs(i,0),fir[tot]=i;}for(int i=1;i<=n;i++){if(du[i]==0)cnt_du[belong[i]]++;}int ansma=0,ansmi=0;for(int i=1;i<=tot;i++){if(siz[i]==1)ansma++;if(check(fir[i],siz[i]))ansma+=siz[i]-1;else ansma+=siz[i]-cnt_du[i];}memset(v,0,sizeof(v));memset(vis,0,sizeof(vis));queue<int>q;for(int i=1;i<=n;i++){if(!du[i])q.push(i);}while(!q.empty()){int u=q.front();q.pop();v[u]=1;if(!vis[a[u]]){v[a[u]]=vis[a[u]]=1,ansmi++;du[a[a[u]]]–;if(!du[a[a[u]]])q.push(a[a[u]]);}}for(int i=1;i<=n;i++){if(!v[i]){int t=i,cnt=0;while(!v[t]){v[t]=1;cnt++;t=a[t];}ansmi+=(cnt+1)/2;}}printf(“%d %d\n”,ansmi,ansma);}

，我想去旅行，一个人背包，一个人旅行，