P1262 间谍网络 题解
题目描述
给你一个有向图,可以付出代价获取一些指定的点。
在获取之后要求能以获取的点为出发点,将整个图都访问到,求最小的代价。
思路
既然需要令总的代价最少,那么如果通过买一个点就可以访问到的所有点,自然会比买两个点的方案更优。
于是自然的就可以联想到可以将图划分成很多个强连通图,只要在这个图中有一个点访问到了,整个强连通图就被访问到了。
既然要求强连通图,那么就自然的需要用到tarjan算法了。
再求出图内的所用强连通图之后对它们进行缩点,这样就只要能访问这个点就可以了。
但是因为在缩点之后就不能简单的遍历这个强连通图,所以我们就需要将这个强连通图中代价最小的一个点记录下来。
这就需要使用一个辅助数组 min_cost
来记录。
具体的实现也很简单,只需要在将栈内的元素弹出时进行比较就可以了。
AC Code
#include<bits/stdc++.h>
using namespace std;
int n,r,p,dfn[3200],low[3200],group[320![](https://www.doittomorrow.xyz/post-images/1704207640718.jpg)0],in[3200],cost[3200],cnt,num,min_cost[3200],ans;
bool vis[3200];
vector<int> v[3200];
stack<int> s;
void tarjan(int x){ //tarjan的板子+缩点
dfn[x]=low[x]=++num;
vis[x]=1;
s.push(x);
for(int i:v[x]){ //依次便利v[x]中的元素赋值给i
if(!dfn[i]){
tarjan(i);
low[x]=min(low[x],low[i]);
}else if(vis[i])
low[x]=min(low[x],dfn[i]);
}if(dfn[x]==low[x]){ //如果有环
group[x]=++cnt;
min_cost[cnt]=cost[x];
vis[x]=0;
while(s.top()!=x){ //栈内有强连通图内的元素
group[s.top()]=cnt;
min_cost[cnt]=min(min_cost[cnt],cost[s.top()]);
vis[s.top()]=0;
s.pop();
}s.pop();
}return ;
}int find(int x){ //寻找这个强连通图内最小的点
for(int i=1;i<=n;i++)
if(group[i]==x)
return i;
return n;
}int main(){
memset(cost,0x3f,sizeof(cost)); //区分是否可以买
cin>>n>>p;
for(int i=1,a,b;i<=p;i++){
cin>>a>>b;
cost[a]=b;
}cin>>r;
for(int i=1,a,b;i<=r;i++){
cin>>a>>b;
v[a].push_back(b); //标记可以通过a直接访问到b
}for(int i=1;i<=n;i++){
if(!dfn[i]&&cost[i]!=0x3f3f3f3f3f) //要判断是否可以买
tarjan(i);
}for(int i=1;i<=n;i++){
for(int j:v[i]){ //依次便利v[i]中的元素赋值给i
if(group[j]!=group[i])
in[group[j]]++;
}
}for(int i=1;i<=cnt;i++){
if(in[i]==0){ //因为入度为0,所以访问到这个具相当于将这一坨都购买了,比买有入度的点划算
ans+=min_cost[i];
if(min_cost[i]==0x3f3f3f3f){ //如果这个区间都不能买就不行
cout<<"NO"<<endl;
cout<<find(i)<<endl;
return 0;
}
}
}cout<<"YES"<<endl;
cout<<ans<<endl;
return 0;
}