P1262 间谍网络’s题解
P1262 间谍网络’s题解
题目描述
给你一个有向图，可以付出代价获取一些指定的点。
在获取之后要求能以获取的点为出发点，将整个图都访问到，求最小的代价。
思路
既然需要令总的代价最少，那么如果通过买一个点就可以访问到的所有点，自然会比买两个点的方案更优。
于是自然的就可以联想到可以将图划分成很多个强连通图，只要在这个图中有一个点访问到了，整个强连通图就被访问到了。
既然要求强连通图，那么就自然的需要用到tarjan算法了。
再求出图内的所用强连通图之后对它们进行缩点，这样就只要能访问这个点就可以了。
但是因为在缩点之后就不能简单的遍历这个强连通图，所以我们就需要将这个强连通图中代价最小的一个点记录下来。
这就需要使用一个辅助数组 \(min\)_\(cost\) 来记录。
具体的实现也很简单，只需要在将栈内的元素弹出时进行比较就可以了。
数组用途
| 数组名 | 用途 |
|---|---|
| \(dfn[i]\) | 储存 \(i\) 在便利的时间戳 |
| \(low[i]\) | 储存以 \(i\) 为起点可以遍历到的时间戳最小的点 |
| \(group[i]\) | 存储点 \(i\) 在经过缩点之后所在的强连通图的编号 |
| \(in[i]\) | 存储点 \(i\) 的入度 |
| \(cost[i]\) | 如果点 \(i\) 可以购买就存储代价，否则为上无穷 |
| \(vis[i]\) | 储存 \(i\) 是否入栈 |
| \(v[i]\) | 储存节点 \(i\) 可以到达的点 |
AC Code
#include<bits/stdc++.h>
using namespace std;
int n,r,p,dfn[3200],low[3200],group[3200],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]; //暂时将最小花费赋值为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;
}