<题目链接>
题目大意：
有n个房间，每个房间都会有一只老鼠。处于第i个房间的老鼠可以逃窜到第ai个房间中。现在要清理掉所有的老鼠，而在第i个房间中防止老鼠夹的花费是ci，问你消灭掉所有老鼠的最少花费。
解题分析：
首先就是要注意老鼠的逃生路线为强连通分量的情况，毫无疑问，这种情况就是在那个强连通分量中的代价最小的房间安装老鼠夹(因为根据老鼠的流通性，只需要在连通分量中安装一个老鼠夹就能捕获所有的老鼠)，所以我们先用Tarjan对这些房间进行缩点。然后我们只需要将那些出度为0的强连通分量的代价相加就行(强连通分量的代价=其中任意点的最小代价)，因为出度为0的强连通分量一定要消除本身的老鼠，并且根据老鼠的流通性，其它出度不为0的老鼠一定也会到达这些出度为0的连通分量中。
#include <bits/stdc++.h>
using namespace std;
const int INF =0x3f3f3f3f;
#define N int(2e5+7)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define srep(i,s,t) for(int i=s;i<t;i++)
#define clr(a,b) memset(a,b,sizeof(a))
int n,top,ans,tot,scc;
int outdeg[N],to[N],stk[N],instk[N],bel[N],dfn[N],low[N],cost[N],val[N];
template<typename T> //读入优化
inline T read(T&x){
x=;;char ch=getchar();
') f|=(ch=='-'),ch=getchar();
+ch-',ch=getchar();
return x=f?-x:x;
}
void Tarjan(int u){
dfn[u]=low[u]=++tot;
stk[++top]=u;instk[u]=;
int v=to[u];
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(instk[v])low[u]=min(low[u],dfn[v]);
if(dfn[u]==low[u]){
++scc;
while(true){
int v=stk[top--];
bel[v]=scc;
if(u==v)break;
}
}
}
int main(){
read(n);
rep(i,,n)read(val[i]);
rep(u,,n){
int v;read(v);to[u]=v;
}
rep(i,,n) if(!dfn[i]){ //Tarjan缩点
Tarjan(i);
}
rep(i,,scc)cost[i]=INF;
rep(i,,n)cost[bel[i]]=min(cost[bel[i]],val[i]); //cost[i]为每个强连通分量中花费最少的点
rep(u,,n){
int v=to[u];
if(bel[u]!=bel[v])outdeg[bel[u]]++; //标记每个强连通分量的出度
}
rep(i,,scc)if(!outdeg[i])ans+=cost[i]; //出度为0的点一定要安装(因为至少要消灭这些点本来的老鼠)，并且只用安装出度为0的点，因为老鼠具有传递性，最终所有老鼠一定会经过这些出度为0的点
printf("%d\n",ans);
}
另一种做法，用并查集判环，DFS找环上的最小代价：
#include<bits/stdc++.h>
using namespace std;
;
int to[N], val[N], pre[N], x[N];
int find(int x){
return x==pre[x]?x:pre[x]=find(pre[x]);
}
int dfs(int x, int root){
if(x==root) return val[x]; //如果是自环，直接返回本身
return min(dfs(to[x], root), val[x]); //寻找环上权值最小的点
}
int main(){
int n;scanf("%d", &n);
;i<=n;i++)scanf("%d", &val[i]), pre[i] = i;
;i<=n;i++)scanf("%d", &to[i]);
;i<=n;i++){ //并查集判独立的连通块(判环或者判独立的点)
; //如果这个点存在环
else pre[find(to[i])] = find(i);
}
;
;i<=n;i++) if(x[i])ans+=dfs(to[i],i);
printf("%d\n",ans);
}
2019-02-18