「Codeforces 1027D」Mouse Hunt

发表于 | | 阅读次数:
字数统计: 607 字

Description

题目链接：Codeforces 1027D

有 $n$ 间屋子和 $1$ 只老鼠，老鼠会从第 $i$ 间房子跑到 $a_i$ 间房子。在每间房子放捕鼠夹都有代价 $c_i$，而老鼠的初始位置可能是任何一个房间，为了保证抓到老鼠（无论老鼠在哪个房间，总有一种路径会经过有捕鼠夹的房子），你需要在若干房间放上捕鼠夹，求最小代价和。

数据范围：$1\le a_i\le n\le 2\cdot 10^5$，$1\le c_i\le 10^4$

Solution

想象成是一张 $n$ 个点、$n$ 条边的基环图，对于每个弱连通块单独处理。

对于第 $i$ 个点，记录是否访问过，如果它还没有答案（起点在 $i$ 时已经能在某个房间抓到老鼠）则进行 $\text{DFS}$。在搜索的过程中，如果遇到了一个已经访问过的点，则说明出现了环。这个环的答案为“搜索中遇到的所有点（用栈维护）的代价最小值”。

代码中， $vis[i]$ 记录是否访问过（用于判环），$mark[i]$ 记录是否已经有答案（用于判断是否需要 $\text{DFS}$）

时间复杂度：$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
 
#include <cstdio>
#include <algorithm>
#include <cctype>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)

char in() {
    static char buf[1000001],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template <class Tp> void read(register Tp &s) {
    s=0;
    register bool neg=0;
    register char c;
    while(!isdigit(c=in())) if(c=='-') neg=1;
    while(s=(s<<3)+(s<<1)+c-48,isdigit(c=in()));
    s=(neg?-s:s);
}

const int N=200005;
int n,a[N],c[N],tot,hd[N],las[N],sz,m,st[N],x[N];
bool vis[N],mark[N];
struct Edge{
    int to,nxt;
}e[N<<1];

void add(int u,int v) {
    e[++tot].to=v;
    e[tot].nxt=hd[u];
    hd[u]=tot;
}
void findloop(int u) {
    if(vis[u]) {
        x[++m]=u;
        while(sz&&st[sz]!=u) x[++m]=st[sz],--sz;
        return;
    }
    vis[u]=1; st[++sz]=u; findloop(a[u]);
}
void dfs(int u) {
    mark[u]=1;
    for(int i=hd[u];i;i=e[i].nxt) if(!mark[e[i].to]) dfs(e[i].to);
}
int main() {
    read(n);
    FOR(i,1,n) read(c[i]);
    FOR(i,1,n) {
        read(a[i]);
        add(i,a[i]); add(a[i],i);
    }
    int ans=0;
    FOR(i,1,n) {
        if(mark[i]) continue;
        sz=0; m=0;
        findloop(i);
        int res=(1<<30);
        FOR(j,1,m) res=std::min(res,c[x[j]]);
        ans+=res;
        dfs(i);
    }
    printf("%d\n",ans);
    return 0;
}
0%