首页 > 代码库 > BZOJ1093 [ZJOI2007]最大半连通子图
BZOJ1093 [ZJOI2007]最大半连通子图
首先，我们要tarjan。。。 然后我们要缩点。。。
注意，缩点的时候两个新建的点会有重边，需要判重
正常的判重方法是bfs一边，但是我YY的比较奇葩，方法下面将。。。
缩好点就变成了一个DAG，然后就类似树形DP的方法求最大权值链
我是用记忆化搜索，当dfs某个点p时用数组vis记录一些东西：
首先vis[x] > 0代表x已经访问过了， vis[x] == p表示vis[x]上次是由p来的，于是就可以去重了。。。
然后就没有然后了，搞定yeah！
1 /************************************************************** 2 Problem: 1093 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1604 ms 7 Memory:31220 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 #include <cstring>13 14 using namespace std;15 const int inf = (int) 1e8;16 struct edges{17 int from, to, next;18 }e[2000005];19 20 int first[100005],tot;21 int dfn[100005], low[100005], w[100005], sum[100005];22 int vis[100005], s[100005], f[100005], g[100005], F[100005];23 int n, m, MOD, X, Y, ans, top, cnt, num, ANS;24 25 void add_edge(int x, int y){26 e[++tot].next = first[x];27 first[x] = tot;28 e[tot].from = x, e[tot].to = y;29 }30 31 void tarjan(int p){32 dfn[p] = low[p] = ++cnt;33 s[++top] = p;34 vis[p] = 1;35 int x, y;36 for (x = first[p]; x; x = e[x].next){37 y = e[x].to;38 if (!vis[y]) tarjan(y);39 if (vis[y] < 2)40 low[p] = min(low[p], low[y]);41 }42 if (dfn[p] == low[p]){43 ++num;44 while (s[top + 1] != p){45 int y = s[top--];46 vis[y] = 2, w[y] = num;47 ++sum[num];48 }49 }50 }51 52 void dfs(int p){53 if (vis[p]) return;54 vis[p] = inf;55 int x, y;56 for (int x = first[p]; x; x = e[x].next){57 y = e[x].to;58 if (vis[y] == p) continue;59 vis[y] = p;60 dfs(y);61 if (f[p] < f[y])62 f[p] = f[y], g[p] = g[y]; else63 if (f[p] == f[y]) g[p] += g[y];64 }65 g[p] %= MOD;66 f[p] += sum[p];67 if (ans < f[p])68 ans = f[p], ANS = g[p]; else69 if (ans == f[p]) ANS += g[p], ANS %= MOD;70 }71 72 int main(){73 scanf("%d%d%d", &n, &m, &MOD);74 for (int i = 1; i <= m; ++i)75 scanf("%d%d", &X, &Y), add_edge(X, Y);76 for (int i = 1; i <= n; ++i)77 if (!vis[i]) tarjan(i);78 79 memset(first, 0, sizeof(first));80 tot = 0;81 for (int i = 1; i <= m; ++i){82 X = e[i].from;83 Y = e[i].to;84 if (w[X] != w[Y]) add_edge(w[X], w[Y]);85 }86 memset(vis, 0, sizeof(vis));87 for (int i = 1; i <= num; ++i)88 if (!first[i]) g[i] = 1;89 for (int i = 1; i <= num; ++i)90 if (!vis[i]) dfs(i);91 printf("%d\n%d\n", ans, ANS % MOD);92 return 0;93 }
(p.s. 各种压代码+卡内存此题status终于上了前两页。。。)
BZOJ1093 [ZJOI2007]最大半连通子图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。