绍兴一中模拟赛3.19—

绍兴一中模拟赛3.19——白驹过隙

本文主要是介绍绍兴一中模拟赛3.19——白驹过隙，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

定义类仙人掌为：

求类仙人掌上的最大独立集大小， $(n < = 50000, m < = 100000)$

Solution

Code

注意 $f [p 2] [p 1] [0] [1]$ 等于 $f [p 1] [p 2] [1] [0]$ ，而不是 $f [p 1] [p 2] [0] [1]$

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define dep(i,a,b) for(register int i=(b);i>=(a);--i)
inline char gc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){int x=0,fl=1;char ch=gc();for(;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;for(;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);return x*fl;
}
const int N=100002;
int n,m,x,y,p1,p2,ans;
queue<int>q;
map<int,bool>p[N];
map<int,int>f[2][2][N];
set<int>to[N];
bool vis[N];
int main(){n=rd(),m=rd();rep(i,1,m){x=rd(),y=rd();to[x].insert(y),to[y].insert(x);p[x][y]=p[y][x]=1;f[0][1][x][y]=f[1][0][x][y]=f[0][1][y][x]=f[1][0][y][x]=1;f[1][1][x][y]=f[1][1][y][x]=-1e9;}rep(i,1,n)if (to[i].size()==2) q.push(i);while (!q.empty()){x=q.front(),q.pop();if (vis[x] || to[x].size()!=2) continue;p1=*to[x].begin(),p2=*(++to[x].begin());f[0][0][p1][p2]+=max(f[0][0][x][p1]+f[0][0][x][p2],f[1][0][x][p1]+f[1][0][x][p2]-1);f[0][1][p1][p2]+=max(f[0][0][x][p1]+f[0][1][x][p2],f[1][0][x][p1]+f[1][1][x][p2]-1)-(f[0][1][p1][p2]>0);f[1][0][p1][p2]+=max(f[0][1][x][p1]+f[0][0][x][p2],f[1][1][x][p1]+f[1][0][x][p2]-1)-(f[1][0][p1][p2]>0);if (!p[p1][p2])ans=max(ans,f[1][1][p1][p2]+=max(f[0][1][x][p1]+f[0][1][x][p2],f[1][1][x][p1]+f[1][1][x][p2]-1)-(f[1][1][p1][p2]>0)*2);ans=max(ans,max(f[0][0][p1][p2],max(f[0][1][p1][p2],f[1][0][p1][p2])));f[0][0][p2][p1]=f[0][0][p1][p2],f[1][0][p2][p1]=f[0][1][p1][p2],f[0][1][p2][p1]=f[1][0][p1][p2],f[1][1][p2][p1]=f[1][1][p1][p2];vis[x]=1;to[p1].erase(x),to[p2].erase(x);to[p1].insert(p2),to[p2].insert(p1);if (to[p1].size()==2) q.push(p1);if (to[p2].size()==2) q.push(p2);}printf("%d",ans);
}