USACO22OPEN-Silver B

前言（Front talk)

$\qquad$有趣的题，竟然可以用最小生成树来做，拓扑排序判环也可以。

网址（Website）

$\qquad$洛谷： USACO22OPEN Visits S

$\qquad$SPOJ：题目详情 - Visits - Super

$\qquad$SPOJ：题解 - Visits - Super

题目（Problem）

$\qquad$Bessie 的 $N$（$2\le N\le 10^5$）个奶牛伙伴（编号为 $1\cdots N$）每一个都拥有自己的农场。对于每个 $1\le i\le N$，伙伴 i 想要访问伙伴 $a_i$（$a_i\neq i$）。

$\qquad$给定 $1\ldots N$ 的一个排列 $(p_1,p_2,\ldots, p_N)$，访问按以下方式发生。

$\qquad$对于 $1$ 到 $N$ 的每一个 $i$：

如果伙伴 $a_{p_i}$ 已经离开了她的农场，则伙伴 $p_i$ 仍然留在她的农场。
否则，伙伴 $p_i$ 离开她的农场去访问伙伴 $a_{p_i}$ 的农场。这次访问会产生快乐的哞叫 $v_{p_i}$ 次（$0\le v_{p_i}\le 10^9$）。

$\qquad$对于所有可能的排列 $p$，计算所有访问结束后可能得到的最大哞叫次数。

输入格式（Input）

$\qquad$输入的第一行包含 $N$。

$\qquad$对于每一个 $1\le i\le N$，第 $i+1$ 行包含两个空格分隔的整数 $a_i$ 和 $v_i$。

输出格式（Output）

$\qquad$输出一个整数，为所求的答案。

$\qquad$注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 “long long”）。

样例（Example）

样例输入

样例输出

提示（Notice）

样例解释

如果 $p=(1,4,3,2)$，则

伙伴 $1$ 访问伙伴 $2$ 的农场，产生 $10$ 次哞叫。
伙伴 $4$ 看到伙伴 $1$ 已经离开了农场，所以无事发生。
伙伴 $3$ 访问伙伴 $4$ 的农场，又产生 $30$ 次哞叫。
伙伴 $2$ 看到伙伴 $3$ 已经离开了农场，所以无事发生。

这样总计得到了 $10+30=40$ 次哞叫。

另一方面，如果 $p=(2,3,4,1)$，则

伙伴 $2$ 访问伙伴 $3$ 的农场，产生 $20$ 次哞叫。
伙伴 $3$ 访问伙伴 $4$ 的农场，产生 $30$ 次哞叫。
伙伴 $4$ 访问伙伴 $1$ 的农场，产生 $40$ 次哞叫。
伙伴 $1$ 看到伙伴 $2$ 已经离开了农场，所以无事发生。

这样总计得到了 $20+30+40=90$ 次哞叫。可以证明这是所有可能的排列 $p$ 中访问结束后得到的最大可能的哞叫次数。

题解（Solution）

$\qquad$以当前农场为 $x$ ，以要去的农场为 $y$ ，以开心值 $v$ 建边。

$\qquad$原图构成了基环树森林，由于环内没有出边，很容易便分析出所有的指向环的点都是可以直接得到的，对于环内，需要去掉一条边权最小的点，于是乎，可以拓扑排序求环，对于每个环遍历一次最小边，去掉贡献即可。

代码（Code）

我的代码（拓扑排序）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
#define P pair<int,int>
#define int long long 
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 101234;

int n,ans,inn[N];
vector<P> ft[N];
bitset<N> vst;

inline int dfs(int x){
	vst[x]=true;
	int minn=inf;for(auto p:ft[x]){
		int y=p.first,v=p.second;
		minn=min(minn,v);
//		printf("%d %d %d min=%d\n",x,y,v,minn);
		if(vst[y]) continue;
		minn=min(dfs(y),minn);
	}return minn;
}

queue<int> q;
void Tuopu(){
	For(x,1,n) if(!inn[x]) q.push(x);
	while(q.size()){
		int x=q.front();q.pop();
		vst[x]=true;
		for(auto p:ft[x]){
			int y=p.first;
			if(--inn[y]==0ll) q.push(y);
		}
	}For(x,1,n) if(!vst[x]) ans-=dfs(x);
	return;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("visits");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n;For(x,1,n){
		int y=input(),v=input();
		ft[x].push_back({y,v});
		inn[y]++;ans+=v;
	}Tuopu();
	cout<<ans<<'\n';
	return 0;
}

cx的代码（最小生成树）

#include <bits/stdc++.h>
using namespace std;
#define N 100010
using ll = long long;
int a[N];
ll v[N];
int n;
int fa[N];
int getfa(int v) {
  return v == fa[v] ? v : fa[v] = getfa(fa[v]);
}
int p[N];
ll ans;
int main() {
  freopen("visits.in", "r", stdin);
  freopen("visits.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) fa[i] = i;
  for (int i = 1; i <= n; ++i) {
    scanf("%d%lld", a + i, v + i);
    p[i] = i;
  }
  sort(p + 1, p + n + 1, [&](int x, int y){return v[x] > v[y];});
  for (int i = 1; i <= n; ++i) {
    int x = getfa(p[i]), y = getfa(a[p[i]]);
    if (x != y) {
      ans += v[p[i]];
      fa[x] = y;
    }
  }
  printf("%lld\n", ans);
  return 0;
}