2017-03-23

【bzoj4316】小C的独立集

仙人掌系列第二题

AC通道

仙人掌最大独立集问题

如果是在树上，直接dp即可：令f[i][0/1]表示i选与不选的答案

放在仙人掌上也是一样的，对于环上的情况单独处理即可

这道题调了1天，原因是环上必须按顺序更新答案

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<vector>
#define FILE "read"
#define MAXN 480010
#define INF (int)1e9
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
struct node{int y,next;}e[MAXN];
int n,m,cnt,top,bcnt,len(1),dfs_clock,Link[MAXN],dfn[MAXN],q[MAXN],f[MAXN][2],g[MAXN][2];
vector<int>ring[MAXN];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
    int x=0,f=1;  char ch=getc();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
    return x*f;
}
void insert(int x,int y){
    e[++len].next=Link[x];Link[x]=len;e[len].y=y;
    e[++len].next=Link[y];Link[y]=len;e[len].y=x;
}
void dfs(int x,int fa){
    dfn[x]=++dfs_clock;
    for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa){
        if(!dfn[e[i].y])  q[++top]=i,dfs(e[i].y,x),--top;
        else if(dfn[e[i].y]<dfn[x]){
            ring[++bcnt].push_back(i);
            for(int j=top;j;--j){
                if(e[q[j]].y==e[i].y)  break;
                ring[bcnt].push_back(q[j]);
            }
        }
    }
}
void build(){
    for(int k=1;k<=bcnt;++k){
        int size=ring[k].size(),top=e[ring[k][0]].y;
        for(int i=0;i<size;++i){
            int temp=e[ring[k][i]].y;
            e[ring[k][i]].y=e[ring[k][i]^1].y=0;
            ring[k][i]=temp;
        }insert(++cnt,top);
        for(int i=1;i<size;++i) insert(ring[k][i],cnt);
    }
}
void dp(int x,int fa){
    if(x<=n){
        f[x][0]=0;  f[x][1]=1;
        for(int i=Link[x];i;i=e[i].next)if(e[i].y&&e[i].y!=fa){
            dp(e[i].y,x);
            if(e[i].y>n)  continue;
            f[x][0]+=max(f[e[i].y][0],f[e[i].y][1]);
            f[x][1]+=f[e[i].y][0];
        }
    }
    else{
        int top=0;
        for(int i=Link[x];i;i=e[i].next)if(e[i].y&&e[i].y!=fa)dp(e[i].y,x);
        for(int i=Link[x];i;i=e[i].next)if(e[i].y){
            g[++top][0]=f[e[i].y][0];
            g[top][1]=f[e[i].y][1];
        }
        for(int i=top-1;i;--i){
            g[i][0]+=max(g[i+1][0],g[i+1][1]);
            g[i][1]+=g[i+1][0];
        }
        f[fa][0]=g[1][0];
        for(int i=1;i<top;++i){
            g[i][0]-=max(g[i+1][0],g[i+1][1]);
            g[i][1]-=g[i+1][0];
        }
        g[top][1]=-INF;
        for(int i=top-1;i;--i){
            g[i][0]+=max(g[i+1][0],g[i+1][1]);
            g[i][1]+=g[i+1][0];
        }
        f[fa][1]=g[1][1];
    }
}
int main(){
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    n=read();  m=read();  cnt=n;
    for(int i=1;i<=m;++i){int x=read(),y=read();insert(x,y);}
    dfs(1,0);  build();  dp(1,0);
    printf("%d\n",max(f[1][0],f[1][1]));
    return 0;
}

本文标题:【bzoj4316】小C的独立集

文章作者:chty

发布时间:2017年03月23日 - 18时35分

最后更新:2018年03月02日 - 17时16分

许可协议:本文为博主原创，未经许可不得转载。