【World Finals】2011 H

【试题编号】
2011 H
【名称】
Mining Your Own Business
【题目大意】
给一个无向图 问最少设置几个点为梯 使得去掉任意一个点 其他点都能到梯
【算法讨论】
求割点 然后求有几个点双联通分量中 只有一个割点 就要放一个梯 如果没有割点要特判 要两个梯
【时空复杂度】
O(n)
O(n)
【code】

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;

//===========================LinkTable=================

const int LTmaxm = 200005;
const int LTmaxn = 200005;

struct line
{
  int to, next;
};

struct Link_Table
{
  line li[LTmaxm];
  int be_[LTmaxn], l;

  int to(int i) { return li[i].to; }
  int next(int i) { return li[i].next; }
  int be(int i) { return be_[i]; }

  void makeline(int fr, int to)
  {
    ++l;
    li[l].next = be_[fr];
    be_[fr] = l;
    li[l].to = to;
  }

  void makeline_double(int fr, int to)
  {
    makeline(fr, to);
    makeline(to, fr);
  }

  void clear()
  {
    l = 0;
    memset(be_, 0, sizeof(be_));
  }
}L;

//===========================LinkTable=================
struct Tarjan
{
    static const int Tmaxn = 200005;
    static const int Tmaxm = 200005;
    int low[Tmaxn], dfn[Tmaxn], tot, t[Tmaxm];

    int tarjan(int now, int fa, Link_Table &L, int *b, int tp)
    {
        dfn[now] = ++tot;
        low[now] = dfn[now];
        int sum = 0, lfa = -1, mi = 0x7fffffff;
        for (int i = L.be(now); i; i = L.next(i))
        {
            int to = L.to(i);
            if (to == fa)
            {
                lfa = i;
                continue;
            }
            if (!dfn[to])
            {
                int t = tarjan(to, now, L, b, tp);
                low[now] = min(low[now], low[to]);
                if (tp)
                    if (low[to] > dfn[now]) b[i] = b[t] = 1;
                ++sum;
                if (low[to] >= dfn[now] && fa != -1) b[now] = 1;
                mi = min(mi, low[to]);
            }
            else low[now] = min(low[now], dfn[to]);
        }
        if (!tp && sum && fa == -1)
            b[now] = sum > 1 ? 1 : 0;
        return lfa;
    }

    void clear()
    {
        memset(low, 0, sizeof(low));
        memset(dfn, 0, sizeof(dfn));
        tot = 0;
    }

    void get_cut_node(Link_Table &L, int n, int *b)
    {
        clear();
        for (int i = 0; i < n; ++i)
            b[i] = 0;
        for (int i = 0; i < n; ++i)
            if (!dfn[i])
                tarjan(i, -1, L, b, 0);
    }

    void get_cut_edge(Link_Table &L, int n, int *b)
    {
        clear();
        for (int i = 0; i < n; ++i)
            b[i] = 0;
        for (int i = 0; i < n; ++i)
            if (!dfn[i])
                tarjan(i, -1, L, b, 1);
        for (int i = 0; i < n; ++i)
        {
            for (int j = L.be(i); j; j = L.next(j))
                ++t[L.to(j)];
            for (int j = L.be(i); j; j = L.next(j))
                if (t[L.to(j)] > 1)
                    b[j] = 0;
            for (int j = L.be(i); j; j = L.next(j))
                --t[L.to(j)];
        }
    }
}T;

int n, b[100005], bb[100005], aans, t[100005], test;
ll ans2;
queue<int> q, q2;

void bfs(int now)
{
    bb[now] = 1;
    q.push(now);
    int ans = 0, tot = 0;
    while (!q.empty())
    {
        ++tot;
        int now = q.front();
        q.pop();
        for (int i = L.be(now); i; i = L.next(i))
        {
            int to = L.to(i);
            if (b[to] && !t[to])
            {
                t[to] = 1;
                q2.push(to);
                ++ans;
            }
            if (b[to] || bb[to]) continue;
            bb[to] = 1;
            q.push(to);
        }
    }
    while (!q2.empty())
    {
        int now = q2.front();
        q2.pop();
        t[now] = 0;
    }
    if (ans == 1)
        ++aans, ans2 *= tot;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    while (scanf("%d", &n), n)
    {
        L.clear();
        int mx = 0;
        for (int i = 0; i < n; ++i)
        {
            int fr, to;
            scanf("%d%d", &fr, &to);
            mx = max(max(fr, mx), to);
            L.makeline_double(fr, to);
        }
        T.get_cut_node(L, n + 10, b);
        memset(bb, 0, sizeof(bb));
        aans = 0;
        ans2 = 1;
        for (int i = 1; i <= mx; ++i)
            if (!bb[i] && !b[i])
                bfs(i);
        if (!aans) printf("Case %d: %d %I64d\n", ++test, 2, ((ll)mx) * (mx - 1) / 2);
        else printf("Case %d: %d %I64d\n", ++test, aans, ans2);
    }
    fclose(stdin);fclose(stdout);
}

BZOJ2030

找割点
对于一个只包含一个割点的块
要有一个出口 可以在这个块中任意不是割点的点上
而对于 有两个割点的块则不需要割点
有一个地方要特判 没有割点 要两个出口

第一次打tarjan = =
就当贴个模板吧。。
—————————————————-

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
using namespace std;
typedef long long ll;
const int maxn = 505;
struct line
{
  int next, to;
}li[maxn * 2];
int be[maxn], l, n, low[maxn], dfn[maxn], m, k, b[maxn], br[maxn];
stack<int> s;
queue<int> q;
ll ans1, ans2;
void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}
void tarjan(int now)
{
  dfn[now] = low[now] = ++m;
  s.push(now);
  br[now] = 2;
  int t = 0;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (!br[to])
    {
      ++t;
      tarjan(to);
      low[now] = min(low[now], low[to]);
    }
    else
    if (br[to] == 2)
      low[now] = min(low[now], dfn[to]);
    if (low[to] >= dfn[now]) b[now] = 1;
  }
  if (now == 1) b[now] = t == 1 ? 0 : 1;
  if (dfn[now] <= low[now])
    while (s.top() != now)
    {
      br[s.top()] = 1;
      s.pop();
    }
}
void bfs(int no)
{
  q.push(no);
  b[no] = -1;
  int tot = 1, g = 0;
  while (!q.empty())
  {
    int now = q.front();
    q.pop();
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (b[to] == -1 || b[to] == no + 10) continue;
      if (b[to])
      {
        ++g, b[to] = no + 10;
        continue;
      }
      b[to] = -1;
      ++tot;
      q.push(to);
    }
  }
  if (g == 1) ans2 = ans2 * tot, ++ans1;
}
int main()
{
  while (cin >> n && n)
  {
    ++k;
    memset(b, 0, sizeof(b));
    memset(be, 0, sizeof(be));
    memset(br, 0, sizeof(br));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    l = 0;
    m = 0;
    ans1 = 0;
    ans2 = 1;
    for (int i = 0; i < n; i++)
    {
      int fr, to;
      scanf(“%d%d”, &fr, &to);
      b[fr] = b[to] = 1;
      makeline(fr, to);
      makeline(to, fr);
    }
    ++n;
    int t = 0;
    for (int i = 1; i <= n; i++)
      if (b[i]) t++;
    memset(b, 0, sizeof(b));
    tarjan(1);
    for (int i = 1; i <= n; i++)
      if (!b[i]) bfs(i);
    if (!ans1) ans1 = 2, ans2 = t * (t – 1) / 2;
    printf(“Case %d: %lld %lld\n”, k, ans1, ans2);
  }

}