小C的独立集

圆方树入门

题目链接

建出圆方树,圆点和圆点之间按正常转移,遇到圆点和方点时,把整个环拉出来,单独跑一遍$DP$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/01/09
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<vector>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 500005
#define maxm 500005
int tot,n,m,a[maxn];
namespace Tree
{
int nx[maxn<<1],to[maxn<<1],hd[maxn<<1],cnt;
inline void add(int u,int v) {
//wrt(u,' '),wrt(v,'\n');
nx[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;
}
int mx;
int dp[maxn][2];
int Dp[maxn][2];
inline void DP(int A,int B,vector < pair<int,int> > x) {
Dp[0][0]=A,Dp[0][1]=B;
rep(i,1,x.size()-1){
Dp[i][0]=max(Dp[i-1][0],Dp[i-1][1])+x[i].second;
Dp[i][1]=Dp[i-1][0]+x[i].first;
}
}
void dfs(int u,int fa) {
cross(i,u)if (to[i]!=fa){
int v=to[i];
if (v>n) {
pair<int,int> ans;
vector< pair<int,int> > vt;
int tt=0;
cross(j,v) {
dfs(to[j],v);
vt.push_back(make_pair(dp[to[j]][1],dp[to[j]][0]));
}
int xx=vt[0].first,yy=vt[0].second;
tt=vt.size()-1;
DP(yy,xx,vt),dp[u][0]+=max(Dp[tt][0],Dp[tt][1]);
DP(yy,-2333333,vt),dp[u][1]+=Dp[tt][0];
}
else {
dp[u][0]+=max(dp[v][0],dp[v][1]);
dp[u][1]+=dp[v][0];
}
}
dp[u][1]++;
}
int calc(int u)
{
dfs(u,0);
return max(dp[u][0],dp[u][1]);
}
}
int dfn[maxn],low[maxn],id;
int sta[maxn],top;
int nx[maxm],to[maxm],hd[maxn],cnt;
int ans;
inline void add(int u,int v){nx[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;}
void tarjan(int u,int fa) {
Tree::mx++;
dfn[u]=low[u]=++id;
sta[++top]=u;
for(int i=hd[u];i;i=nx[i]) if (to[i]!=fa) {
int v=to[i];
if (!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if (low[v]==dfn[u]) { //对于一般图,此处为>=;对于仙人掌,此处为==
tot++;
while(sta[top]!=v)
Tree::add(n+tot,sta[top--]);
Tree::add(n+tot,sta[top--]);
Tree::add(u,n+tot);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void init(int n)
{
rep(i,1,n) if (!dfn[i]) {
Tree::mx=0;
tarjan(i,0),ans+=Tree::calc(i);
}
}
int main()
{
n=rd(),m=rd();
rep(i,1,m) {
int x=rd(),y=rd();
add(x,y),add(y,x);
}
init(n);
wrt(ans,'\n');
}
avatar
最短路