bzoj2208[Jsoi2010]连通数

HINT

对于100%的数据&＃xff0c;N不超过2000。

原来我想的是用树形dp搞&＃xff0c;但是发现会重复统计

比如3个点3条边&＃xff0c;1->2&＃xff0c;2->3&＃xff0c;1->3&＃xff0c;先建反边按拓扑排序的顺序做&＃xff1a;3更新1、2&＃xff0c;但是2更新1的时候1已经统计过了3&＃xff0c;所以重复记数

考虑状压一下&＃xff0c;保存每个点能到达的点&＃xff0c;更新的时候就不会重复统计了

说到状压&＃xff0c;必须讲下bitset大法好&＃xff01;

当然缩点还是省不了的

#include #include #include #define LL long long #define N 2010 using namespace std; inline LL read() {LL x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}return x*f; } int n,cnt,cnt2,cnt3,tt,ans; bitset flag[N]; char ch[N]; struct edge{int to,next;}e[N*N],e2[N*N]; int head[N],head2[N],dfn[N],low[N]; int belong[N],size[N],son[N]; int zhan[N],top,q[N]; bool inset[N],mrk[N]; int I[N],O[N]; inline void insert(int u,int v) {e[&＃43;&＃43;cnt].to&＃61;v;e[cnt].next&＃61;head[u];head[u]&＃61;cnt; } inline void ins(int u,int v) {e2[&＃43;&＃43;cnt2].to&＃61;v;e2[cnt2].next&＃61;head2[u];head2[u]&＃61;cnt2; } inline void dfs(int x) {dfn[x]&＃61;low[x]&＃61;&＃43;&＃43;tt;zhan[&＃43;&＃43;top]&＃61;x;inset[x]&＃61;1;for (int i&＃61;head[x];i;i&＃61;e[i].next)if (!dfn[e[i].to]){dfs(e[i].to);low[x]&＃61;min(low[x],low[e[i].to]);}else if (inset[e[i].to]) low[x]&＃61;min(low[x],dfn[e[i].to]);if (dfn[x]&＃61;&＃61;low[x]){int p&＃61;-1;cnt3&＃43;&＃43;;while (p!&＃61;x){p&＃61;zhan[top--];belong[p]&＃61;cnt3;inset[p]&＃61;0;size[cnt3]&＃43;&＃43;;}} } inline void tarjan() {for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)if (!dfn[i])dfs(i); } int main() {n&＃61;read();for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%s",ch&＃43;1);for (int j&＃61;1;j<&＃61;n;j&＃43;&＃43;)if (ch[j]&＃61;&＃61;&＃39;1&＃39;)insert(i,j);}tarjan();for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for (int j&＃61;head[i];j;j&＃61;e[j].next)if (belong[e[j].to]!&＃61;belong[i]){ins(belong[e[j].to],belong[i]);flag[belong[i]][belong[e[j].to]]&＃61;1;I[belong[i]]&＃43;&＃43;;O[belong[belong[e[i].to]]]&＃43;&＃43;;}int t&＃61;0,w&＃61;0;for (int i&＃61;1;i<&＃61;cnt3;i&＃43;&＃43;){flag[i][i]&＃61;1;if (!I[i])q[w&＃43;&＃43;]&＃61;i,mrk[i]&＃61;1;}while (t!&＃61;w){int now&＃61;q[t&＃43;&＃43;];for (int i&＃61;head2[now];i;i&＃61;e2[i].next){int to&＃61;e2[i].to;if (mrk[to])continue;flag[to]|&＃61;flag[now];I[to]--;if (!I[to]){mrk[to]&＃61;1;q[w&＃43;&＃43;]&＃61;to;}}}for (int i&＃61;1;i<&＃61;cnt3;i&＃43;&＃43;)for (int j&＃61;1;j<&＃61;cnt3;j&＃43;&＃43;)if (flag[i][j])ans&＃43;&＃61;size[i]*size[j];printf("%d\n",ans);return 0; }