题目

很急的灾

分析

……这个题……

难道不是很裸、很简单吗？？？

首先，我们看到题目中的每个村庄内部，每家每户都可以互相到达，一个避难所内部也都可以互相到达，很容易想到它们都是强连通分量。我们只需要使用Tarjian进行缩点，这些村庄，避难所就都变成一个个的节点了。然后，根据题目中的村庄之间不能到达，避难所之间不能到达，那么很明显这就会组成一张二分图。然后只需要进行二分图最大匹配，不就行啦吗？？？

到底有什么难的呀？

代码

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
#include <bits/stdc++.h>

using namespace std;

inline long long read()
{
    long long x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
void write(const long long &x)
{
    if (!x)
    {
        putchar('0');
        return;
    }
    char f[100];
    long long tmp = x;
    if (tmp < 0)
    {
        tmp = -tmp;
        putchar('-');
    }
    int s = 0;
    while (tmp > 0)
    {
        f[s++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (s > 0)
    {
        putchar(f[--s]);
    }
}

const int N = 3500010, M = 3500010;
int ver[M], Next[M], head[N], dfn[N], low[N];
int in_stack[N], in_DCC_num[N];
int ver_of_DCC[M], next_of_DCC[M], head_of_DCC[N], tot_DCC_Nodes;
stack<int> Nodes_of_DCCs;
vector<int> DCCs[N];
int tot, num, cnt;

void add(int x, int y)
{
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void add_DCC_Node(int x, int y)
{
    ver_of_DCC[++tot_DCC_Nodes] = y, next_of_DCC[tot_DCC_Nodes] = head_of_DCC[x], head_of_DCC[x] = tot_DCC_Nodes;
}
void tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    Nodes_of_DCCs.push(x);
    in_stack[x] = 1;
    for (int i = head[x]; i; i = Next[i])
        if (!dfn[ver[i]])
        {
            tarjan(ver[i]);
            low[x] = min(low[x], low[ver[i]]);
        }
        else if (in_stack[ver[i]])
            low[x] = min(low[x], dfn[ver[i]]);
    if (dfn[x] == low[x])
    {
        cnt++;
        int y;
        do
        {
            y = Nodes_of_DCCs.top();
            Nodes_of_DCCs.pop();
            in_stack[y] = 0;
            in_DCC_num[y] = cnt, DCCs[cnt].push_back(y);
        } while (x != y);
    }
}

bool visit[3500090];
int match[3500090];

bool dfs(int x)
{
    for (int i = head_of_DCC[x]; i; i = next_of_DCC[i])
    {
        int y;
        if (!visit[y = ver_of_DCC[i]])
        {
            visit[y] = true;
            if (!match[y] || dfs(match[y]))
            {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

int answer = 0;
int totDOT;
int totROAD;

int main()
{
    totDOT = read();
    totROAD = read();
    for (int i = 1; i <= totROAD; i++)
    {
        add(read(), read());
    }
    for (int i = 1; i <= totDOT; i++)
    {
        if (!dfn[i])
        {
            tarjan(i);
        }
    }
    for (int i = 1; i <= totDOT; i++)
    {
        for (int j = head[i]; j; j = Next[j])
        {
            int y = ver[j];
            if (in_DCC_num[i] == in_DCC_num[y])
                continue;
            add_DCC_Node(in_DCC_num[i], in_DCC_num[y]);
        }
    }
    for (int i = 1; i <= cnt; i++)
    {
        memset(visit, 0, sizeof(visit));
        if (dfs(i))
        {
            answer++;
        }
    }
    write(answer);
    return 0;
} //LikiBlaze Code

emm……不就是这些？？？