#include <cstdio>
#include <algorithm>
#include <functional>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif

typedef long long int ll;

namespace IPT {//读入优化
  const int L = 1000000;
  char buf[L], *front=buf, *end=buf;
  char GetChar() {
    if (front == end) {
      end = buf + fread(front = buf, 1, L, stdin);
      if (front == end) return -1;
    }
    return *(front++);
  }
}

template <typename T>//这个题的数据是1e7左右，要用fread,不然读入完时间就到了
inline void qr(T &x) {
  char ch = IPT::GetChar(), lst = ' ';
  while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
  while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
  if (lst == '-') x = -x;
}

const int maxn = 1000006;

struct Edge {
  int v;
  Edge *nxt;

  Edge(const int _v, Edge *h) : v(_v), nxt(h) {}
};
Edge *hd[maxn];

int n, m, k, vistime, top, scnt;
int MU[maxn], dfn[maxn], low[maxn], stack[maxn], belong[maxn], minv[maxn];//belong统计缩点后每个点的入度（有时候是一个大环的入度）
bool instack[maxn], haveind[maxn];

void tarjan(const int u);

int main() {
  freopen("zay.in", "r", stdin);
  freopen("zay.out", "w", stdout);
  qr(n); qr(m); qr(k); MU[0] = 2333;
  for (int i = 1; i <= n; ++i) qr(MU[i]);//读入点权
  for (int i = 1, u, v; i <= m; ++i) {
    u = v = 0; qr(u); qr(v);
    hd[u] = new Edge(v, hd[u]);
  }
  for (int i = 1; i <= n; ++i) if (!dfn[i]) {
    tarjan(i);//缩点，我们待会再扯
  }
  for (int u = 1; u <= n; ++u) {
    for (auto e = hd[u]; e; e = e->nxt) if (belong[u] != belong[e->v]) //e->nxt就是找下一条边，如果两个环的入度不相等，就满足排序取前k个点的思路是对的
{
      haveind[belong[e->v]] = true;//e->v就是e这条边的终点v
    }
  }
  for (int i = 1; i <= scnt; ++i) if (!haveind[i]) {
    MU[minv[i]] = 0;
  }
  std::nth_element(MU + 1, MU + 1 + k, MU + 1 + n,//这里是排序（取前k个的写法，也可以sort,不过这个比sort省时间） std::greater<int>());
  int ans = 0;
  for (int i = 1; i <= k; ++i) {
    ans += MU[i];
  }
  printf("%d\n", ans);
  return 0;
}

void tarjan(const int u) {//缩点
  dfn[u] = low[u] = ++vistime;
  instack[stack[++top] = u] = true;
  for (auto e = hd[u]; e; e = e->nxt) {
    int v = e->v;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = std::min(low[u], low[v]);
    } else if (instack[v]) {
      low[u] = std::min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    int v, &_mv = minv[++scnt];
    do {
      instack[v = stack[top--]] = false;
      belong[v] = scnt;
      if (MU[v] < MU[_mv]) _mv = v;
    } while (v != u);
  }
}

我们扯一下缩点（Tarjan）

我们先来看一棵十分强大的dfs树（dfs树就是在有向图上，从一个点开始dfs，最终遍历的所有点和边可以构成一棵树，这棵树就是dfs树）

就像上图，从子孙节点指向祖宗节点的边叫返祖边，从一个节点指向兄弟节点的儿子的边叫横叉边，从祖宗节点指向孙子节点的边叫前向边

显然，这三种边中，只有返祖边会形成环，所以我们只要管返祖边就好了。

每个点不好表示，我们可以先给在dfs树上的节点一个编号，保证先遍历到的点的编号小。dfs[n]就是节点n的编号。

我们的目的是找出返祖边，并且把形成环的这一部分弄成一个大点。所以我们再建立一个数组low,low[i]指从i点能够遍历到的在dfs树上最靠上的点的编号（也就是最祖宗的点的编号）

for example(点内的数字是点的编号)

low[4]=1，因为4可以返回到2,2遍历到3,3返回到1

通过low，就可以找到返祖边，进而缩成一个点

程序实现：

将未dfs过的点进行dfs,形成dfs树，并且把遍历到的点入栈，遍历点的出边。low[i]初始化为i。如果有点的出边的终点是之前dfs过的点，则弹栈，一直弹到终点（把终点弹出），将中间所有弹出的点的low设置为终点，并将点权加和。

代码（from zay）

void tarjan(const int u) {//其实就是上面那段代码的最后一部分辣
  dfn[u] = low[u] = ++vistime;
  instack[stack[++top] = u] = true;//标记是否在栈里面
  for (auto e = hd[u]; e; e = e->nxt) {
    int v = e->v;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = std::min(low[u], low[v]);//这里考虑到v可能会有返祖边，所以取min
    } else if (instack[v]) {
      low[u] = std::min(low[u], dfn[v]);//不确保u的返祖边指向的节点比v低
    }
  }
  if (dfn[u] == low[u]) {//如果没有形成环，就不缩点
    int v, &_mv = minv[++scnt];
    do {
      instack[v = stack[top--]] = false;
      belong[v] = scnt;
      if (MU[v] < MU[_mv]) _mv = v;
    } while (v != u);//也可以直接写while循环
  }
}

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。