锦鲤抄 题解
- 首先考虑有向无环图的情况：
我们发现，只要按照拓扑序倒序删点的话，所有的的有入度的点都是可以删掉的。
- 有环图：
此时，与有向无环图情况不同的地方即是多了一些强连通分量，于是考虑缩点转化为有向无环图，接下来只需考虑这些强连通分量内部如何处理即可。
若这个强连通分量有入度，画图可知只要按照一定顺序，整个强连通分量都是可以删去的。
若这个强连通分量没有入度，显然的是至少有一个点删不掉，于是我们贪心的不删点权最小的点即可。
同时，若这个强连通分量内部有自环，整个强连通分量也是可以全部删去的，和这个强连通分量有入度的原理相同。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x7fffffff
const ll maxn=2e6+10;
ll flag[maxn],scc[maxn],per[maxn];
ll n,m,k,U[maxn],V[maxn];
ll low[maxn],vis[maxn],dfn[maxn],tot,cnt;
ll f[maxn],minn[maxn],val[maxn];
vector<ll> G[maxn],si[maxn];
stack<ll> q;
ll p[maxn];
inline bool cmp(ll x,ll y) {return x>y;}
inline void solve(ll u) {
q.pop();
if (val[u]<minn[tot]) {f[u]=1;minn[tot]=val[u];}
per[u]=tot;vis[u]=0;si[tot].push_back(u);
}
inline void tarjan(ll u) {
vis[u]=dfn[u]=low[u]=++cnt;
q.push(u);
for (ll i=0;i<G[u].size();++i) {
ll v=G[u][i];
if (!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (vis[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u]) {
++tot;
minn[tot]=inf;
while (q.top()!=u) solve(q.top());
solve(u);
}
}
inline ll in() {
char a=getchar();
ll t=0,f=1;
while(a<'0'||a>'9') {if (a=='-') f=-1;a=getchar();}
while(a>='0'&&a<='9') {t=(t<<1)+(t<<3)+a-'0';a=getchar();}
return t*f;
}
signed main() {
n=in(),m=in(),k=in();
for (ll i=1;i<=n;++i) val[i]=in();
for (ll i=1;i<=m;++i) {
U[i]=in(),V[i]=in();
G[U[i]].push_back(V[i]);
}
for (ll i=1;i<=n;++i) if (!dfn[i]) tarjan(i);
for (ll i=1;i<=m;++i) {
if (U[i]==V[i]||per[U[i]]!=per[V[i]]) flag[per[V[i]]]=1;
}
ll T=0;
for (ll i=1;i<=tot;++i) {
// printf("%lld\n",flag[i]);
for (ll j=0;j<si[i].size();++j) {
ll u=si[i][j];
if (f[u]&&minn[i]==val[u]&&!flag[i]) continue;
p[++T]=val[u];
}
}
// printf("%lld\n",T);
sort(p+1,p+1+T,cmp);
ll ans=0;
for (ll i=1;i<=k;++i) ans+=p[i];
printf("%lld",ans);
return 0;
}