首页 > 其他 > 详细

luogu P3225 HNOI2012 矿场搭建

时间:2019-06-20 00:00:11      阅读:115      评论:0      收藏:0      [点我收藏+]

  这个题一开始想法偏了,看了题解才搞明白的。

  考虑对于每个vdcc(点双联通分量),如果不与任何一个割点相连,就至少要在块内预留两个逃生出口作为双保险。而如果与且仅与某一个割点相连的话,只要在块内建造一个点,就可以同时防范割点塌掉/逃生点塌掉的情况。而只要与两个及以上的割点相连,无论哪边塌掉,都可以从另一边逃生。

  至于建造方法数,需要用到组合和乘法原理来求解。

  一种思路是,先跑出所有的割点,然后搜索每个联通块与哪几个割点相连。这就需要记录每一个dcc内除割点外有几个点,用组合数算出建造1/2个出口分别有多少种方式。

  另外想到一种方法:我们可以不搜索,而在求割点时把vdcc的元素记录下来,最后遍历每个vdcc找割点即可。灵感来自于vdcc缩点,省去了搜索时防重复计算的一大堆特判QwQ。

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <cctype>  
  5. #include <vector>  
  6. #include <stack>  
  7. #define maxn 510  
  8. using namespace std;  
  9. int n, cas, N;   
  10. template <typename T>  
  11. void read(T &x) {  
  12.     x = 0;  
  13.     int f = 1;  
  14.     char ch = getchar();  
  15.     while (!isdigit(ch)) {  
  16.         if (ch == ‘-‘) f = -1;  
  17.         ch = getchar();  
  18.     }  
  19.     while (isdigit(ch))  
  20.         x = x * 10 + (ch ^ 48),   
  21.         ch = getchar();  
  22.     x *= f;  
  23. }  
  24. struct E {  
  25.     int to, nxt;  
  26. } edge[maxn << 1];  
  27. int head[maxn], top = 1;  
  28. inline void insert(int u, int v) {  
  29.     edge[++top] = (E) {v, head[u]};  
  30.     head[u] = top;  
  31. }  
  32. int dfn[maxn], low[maxn], timer, root, cnt;  
  33. int weight, Cut, vis[maxn], vdcc_cnt;  
  34. bool cut[maxn];  
  35. void dfs(int u) {  
  36.     dfn[u] = low[u] = ++timer;  
  37. /*  if (u == root && head[u] == 0) { 
  38.         cnt_v[++cnt] = 1; 
  39.         return; 
  40.     } ¹ÂÁ¢µã£ºÕâÊDz»¿ÉÄܵÄÇé¿ö*/   
  41. //  sta.push(u);  
  42.     int flag = 0;  
  43.     for (int i = head[u]; i; i = edge[i].nxt) {  
  44.         int v = edge[i].to;  
  45.         if (!dfn[v]) {  
  46.             dfs(v);  
  47.             low[u] = min(low[u], low[v]);  
  48.             if (dfn[u] == low[v]) {  
  49.                 ++flag;  
  50.                 if (u != root || flag > 1) {  
  51.                     cut[u] = true;  
  52.                 }  
  53.             }  
  54.         } else  
  55.             low[u] = min(low[u], dfn[v]);  
  56.     }  
  57. }  
  58. void tarjan() {  
  59.     for (int i = 1; i <= N; ++i)   
  60.         if (!dfn[i])   
  61.             root = i, dfs(i);   
  62. }  
  63. void judge(int u) {  
  64.     vis[u] = vdcc_cnt;  
  65.     ++weight;     
  66.     for (int i = head[u]; i; i = edge[i].nxt) {  
  67.         int v = edge[i].to;  
  68.         if (cut[v] && vis[v] != vdcc_cnt) {  
  69.             ++Cut;  
  70.             vis[v] = vdcc_cnt;  
  71.         }  
  72.         if (!vis[v])  
  73.             judge(v);  
  74.     }  
  75.     return;  
  76. }  
  77. void solve() {  
  78.     int ans1 = 0;  
  79.     unsigned long long ans2 = 1;  
  80.     for (int i = 1; i <= N; i++)  
  81.         if (!vis[i] && !cut[i]) {  
  82.             weight = Cut = 0;  
  83.             ++vdcc_cnt;  
  84.             judge(i);  
  85.             if (Cut == 0) {  
  86.                 ans1 += 2;  
  87.                 ans2 *= weight * (weight - 1) / 2;  
  88.             } else if (Cut == 1) {  
  89.                 ans1 += 1;  
  90.                 ans2 *= weight;  
  91.             }  
  92.         }  
  93.     printf("Case %d: %d %lld\n", cas, ans1, ans2);  
  94.     return;  
  95. }  
  96. void init() {  
  97.     top = 1, cnt = 0, timer = 0;  
  98.     vdcc_cnt = 0;  
  99.     N = 0;  
  100.     memset(head, 0, sizeof(head));  
  101.     memset(dfn, 0, sizeof(dfn));  
  102.     memset(low, 0, sizeof(low));  
  103.     memset(vis, 0, sizeof(vis));  
  104.     memset(cut, 0, sizeof(cut));  
  105. //  for (int i = 1; i <= 1000; ++i)  
  106. //      edge[i] = (E) {0, 0};  
  107. }  
  108. int main() {  
  109.     while (1) {  
  110.         read(n);  
  111.         ++cas;  
  112.         if (!n) return 0;  
  113.         init();  
  114.         int u, v;  
  115.         for (int i = 1; i <= n; ++i) {  
  116.             read(u), read(v);  
  117.             insert(u, v), insert(v, u);  
  118.             N = max(max(u, v), N);  
  119.         }  
  120.         tarjan();  
  121.         solve();  
  122.     }  
  123. return 0;  
  124. }  
  125. /////////第二种
    1. #include <iostream>  
    2. #include <cstdio>  
    3. #include <cstring>  
    4. #include <cctype>  
    5. #include <vector>  
    6. #include <stack>  
    7. #define maxn 510  
    8. using namespace std;  
    9. int n, cas, N;   
    10. template <typename T>  
    11. void read(T &x) {  
    12.     x = 0;  
    13.     int f = 1;  
    14.     char ch = getchar();  
    15.     while (!isdigit(ch)) {  
    16.         if (ch == ‘-‘) f = -1;  
    17.         ch = getchar();  
    18.     }  
    19.     while (isdigit(ch))  
    20.         x = x * 10 + (ch ^ 48),   
    21.         ch = getchar();  
    22.     x *= f;  
    23. }  
    24. struct E {  
    25.     int to, nxt;  
    26. } edge[maxn << 1];  
    27. int head[maxn], top = 1;  
    28. inline void insert(int u, int v) {  
    29.     edge[++top] = (E) {v, head[u]};  
    30.     head[u] = top;  
    31. }  
    32. int dfn[maxn], low[maxn], timer, root, cnt;  
    33. vector<int> vdcc[maxn];  
    34. stack<int> sta;  
    35. bool cut[maxn];  
    36. void dfs(int u) {  
    37.     dfn[u] = low[u] = ++timer;  
    38. /*  if (u == root && head[u] == 0) { 
    39.         cnt_v[++cnt] = 1; 
    40.         return; 
    41.     } 不可能有孤立点*/   
    42.     sta.push(u);  
    43.     int flag = 0;  
    44.     for (int i = head[u]; i; i = edge[i].nxt) {  
    45.         int v = edge[i].to;  
    46.         if (!dfn[v]) {  
    47.             dfs(v);  
    48.             low[u] = min(low[u], low[v]);  
    49.             if (dfn[u] == low[v]) {  
    50.                 ++flag;  
    51.                 if (u != root || flag > 1)   
    52.                     cut[u] = true;  
    53.                 ++cnt;  
    54.                 int x;  
    55.                 do {  
    56.                     x = sta.top();  
    57.                     sta.pop();  
    58.                     vdcc[cnt].push_back(x);  
    59.                 } while (x != v);  
    60.                 vdcc[cnt].push_back(u);  
    61.             }  
    62.         } else  
    63.             low[u] = min(low[u], dfn[v]);  
    64.     }  
    65. }  
    66. void tarjan() {  
    67.     for (int i = 1; i <= N; ++i)   
    68.         if (!dfn[i])   
    69.             root = i, dfs(i);   
    70. }  
    71. void solve() {  
    72.     int ans1 = 0;  
    73.     unsigned long long ans2 = 1;  
    74.     for (int i = 1; i <= cnt; ++i) {  
    75.         int Cut = 0, w = vdcc[i].size();  
    76.         for (int j = 0; j < w; ++j)  
    77.             if (cut[vdcc[i][j]])  
    78.                 ++Cut;  
    79.         if (Cut == 0)  
    80.             ans1 += 2, ans2 *= w * (w - 1) / 2;  
    81.         if (Cut == 1)  
    82.             ans1 += 1, ans2 *= w - Cut;  
    83.     }  
    84.     printf("Case %d: %d %lld\n", cas, ans1, ans2);  
    85.     return;  
    86. }  
    87. void init() {  
    88.     for (int i = 1; i <= cnt; ++i)  
    89.         vdcc[i].clear();  
    90.     top = 1, cnt = 0, timer = 0;  
    91.     N = 0;  
    92.     memset(head, 0, sizeof(head));  
    93.     memset(dfn, 0, sizeof(dfn));  
    94.     memset(low, 0, sizeof(low));  
    95.     memset(cut, 0, sizeof(cut));  
    96.     while (!sta.empty()) sta.pop();  
    97.   
    98. }  
    99. int main() {  
    100.     while (1) {  
    101.         read(n);  
    102.         ++cas;  
    103.         if (!n) return 0;  
    104.         init();  
    105.         int u, v;  
    106.         for (int i = 1; i <= n; ++i) {  
    107.             read(u), read(v);  
    108.             insert(u, v), insert(v, u);  
    109.             N = max(max(u, v), N);  
    110.         }  
    111.         tarjan();  
    112.         solve();  
    113.     }  
    114.     return 0;  
    115. }  
    116. //这个排版好难……

luogu P3225 HNOI2012 矿场搭建

原文:https://www.cnblogs.com/TY02/p/11055042.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!