Codeforces 1027D Mouse Hunt 题解

发表于 | 更新于 | 阅读次数：
本文字数： 926 字 | 阅读时长 ≈ 4 分钟

题意简述

n个房间，有一只老鼠可能出现在任意一个房间，并且老鼠在第i个房间出现时，下一秒就会运动到第ai个房间。需要放陷阱确保老鼠不管在哪里出现都会被抓。在第i个房间放陷阱成本ci，输出最少需要多少成本完成题目要求
（vjudge翻译）（又是蒯的）

思路框架

我们把$i$向$a_i$连边，就得到了老鼠的走向图。然后我们在走向图上找到所有强连通分量。显然，同一个强连通分量（由于每个点有且仅有唯一的出边，所以一个强连通分量肯定就是一个环）中，我们只要在其中一个位置布置陷阱即珂。那么我们就在花费最小的位置布置好了。

那么，哪些强连通分量中要布置陷阱呢？只有缩点后出度为$0$的强连通分量需要布置，因为别的强连通分量会不断的往下走，肯定会走到一个出度为$0$的强连通分量。

总结一下思路：

  1. 找出所有强连通分量，求出里面最小的花费，令它为这个强连通分量的花费。
  2. 答案=所有出度为0的强连通分量花费的和。

代码

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

#include <bits/stdc++.h>using namespace std;
namespace Flandre_Scarlet
{
    #define N 255555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)

    class Graph
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<1];
            void clear(int _V=N,int _E=N<<1) 
            {
                memset(Ed,-1,sizeof(Edge)*(_E));
                memset(head,-1,sizeof(int)*(_V));
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w=1)
            {
                Ed[++EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}
            int Start(int u) {return head[u];}
            int To(int u){return Ed[u].To;}
            int Label(int u){return Ed[u].Label;}
            int Next(int u){return Ed[u].Next;}
    }G;
    
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int n,a[N],c[N];
    void Input()
    {
        R1(n);
        F(i,1,n) R1(c[i]);
        F(i,1,n) R1(a[i]);
    }
    
    int DFSid[N],low[N],Time=0;
    stack<int> S;bool In[N];
    int SCCid[N],SCCcnt; 
    int Min[N]; //Min[i]: 编号为i的强连通分量的花费
    void Tarjan(int u)
    {
        DFSid[u]=low[u]=++Time;
        S.push(u);In[u]=1;
        Tra(i,u)
        {int v=__v;
            if (!DFSid[v]) {Tarjan(v);low[u]=min(low[u],low[v]);}
            else if (In[v]){low[u]=min(low[u],low[v]);}
        }
        if (DFSid[u]==low[u])
        {
            ++SCCcnt;
            int top;
            do
            {
                top=S.top();S.pop();In[u]=0;
                SCCid[top]=SCCcnt;
                Min[SCCcnt]=min(Min[SCCcnt],c[top]);
            }while(top!=u);
        }
    }
    int odeg[N]; //out degree，出度
    void Soviet()
    {
        G.clear();
        F(i,1,n) G.AddEdge(i,a[i]);

        while(!S.empty()) S.pop();
        Time=SCCcnt=0;
        FK(DFSid);FK(low);
        MEM(Min,0x3f);
        F(i,1,n) if (!DFSid[i]) Tarjan(i);

        F(u,1,n) Tra(i,u)
        {int v=__v;
            int su=SCCid[u],sv=SCCid[v];
            if (su!=sv) ++odeg[su];
        } 
        int ans=0;
        F(i,1,SCCcnt) if (!odeg[i]) ans+=Min[i]; //出度为0的强连通分量的花费的和
        printf("%d\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w