codeforce round#49D---Mouse Hunt
程序员文章站
2022-04-02 22:09:32
...
codeforce round#49D---Mouse Hunt
可以将题目转化为一个图,每个节点只有一个出度,对于入度为0的点,如果在该点放陷阱,则必须再次在其后继节点放,因而有了额外的花费;不断去掉入度为0的节点后发现最后剩下的一定是一个环,而且不可能是叠加环(因为每个节点出度为1),这时候只需要处理每一个环即可,即取环中花费最小的节点安放陷阱
#include<cstdio>
#include<queue>
using namespace std;
const int n_max=2e5+5;
int idegree[n_max],cost[n_max],trans[n_max];
int main()
{
int n;
queue<int>q;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&cost[i]);
for(int i=1;i<=n;++i)
{
scanf("%d",&trans[i]);
++idegree[trans[i]];
}
for(int i=1;i<=n;++i)
{
if(idegree[i]==0)
q.push(i);
}
while(!q.empty())
{
int x=q.front();
q.pop();
--idegree[trans[x]];
if(idegree[trans[x]]==0)
q.push(trans[x]);
}
int ans=0;
for(int i=1;i<=n;++i)
{
if(idegree[i]!=0)
{
int temp=cost[i],u=trans[i];
idegree[i]=0;
while(idegree[u]!=0)
{
temp=min(temp,cost[u]);
idegree[u]=0;
u=trans[u];
}
ans+=temp;
}
}
printf("%d\n",ans);
}
推荐阅读
-
codeforce 685 div2 C
-
CodeForce:16C-Monitor“编程题”
-
codeforce 1064D bfs
-
Codeforce 1270 G. Subset with Zero Sum(数学 + 建图构造 + 思维)
-
Treasure Hunt POJ - 1066
-
POJ 1066 Treasure Hunt
-
Educational Codeforces Round 23#A. Treasure Hunt
-
Codeforce 622 F. The Sum of the k-th Powers(拉格朗日插值求k次幂之和,拉格朗日插值公式)
-
codeforce-892B Wrath(递推)
-
codeforce 686div3 F Array Partition单调栈