USACO22OPEN-Silver B

前言（Front talk)

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

网址（Website）

洛谷： USACO22OPEN Visits S

SPOJ：题目详情 - Visits - Super

SPOJ：题解 - Visits - Super

题目（Problem）

Bessie 的（）个奶牛伙伴（编号为）每一个都拥有自己的农场。对于每个，伙伴 i 想要访问伙伴（）。

给定的一个排列，访问按以下方式发生。

对于到的每一个：

如果伙伴已经离开了她的农场，则伙伴仍然留在她的农场。
否则，伙伴离开她的农场去访问伙伴的农场。这次访问会产生快乐的哞叫次（）。

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

输入格式（Input）

输入的第一行包含。

对于每一个，第行包含两个空格分隔的整数和。

输出格式（Output）

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

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

样例（Example）

样例输入

样例输出

提示（Notice）

样例解释

如果，则

伙伴访问伙伴的农场，产生次哞叫。
伙伴看到伙伴已经离开了农场，所以无事发生。
伙伴访问伙伴的农场，又产生次哞叫。
伙伴看到伙伴已经离开了农场，所以无事发生。

这样总计得到了次哞叫。

另一方面，如果，则

伙伴访问伙伴的农场，产生次哞叫。
伙伴访问伙伴的农场，产生次哞叫。
伙伴访问伙伴的农场，产生次哞叫。
伙伴看到伙伴已经离开了农场，所以无事发生。

这样总计得到了次哞叫。可以证明这是所有可能的排列中访问结束后得到的最大可能的哞叫次数。

题解（Solution）

以当前农场为，以要去的农场为，以开心值建边。

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

代码（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;
}