POI2009SLO-Elephants

标签：cnt POI2009SLO val Elephants int mn mi vis

#POI #Year2009 #贪心 #数学 

建图，对于每个环，有两种可行的方案，

• 是这个环内部操作，需要的代价为 \(mi\times (cnt-2)\) ， \(mi\) 为这个环中的最小值， \(cnt\) 为这个环的长度
• 还可以用环外的一个点，需要的代价为 \(mn\times (cnt+1)+mi\)
  直接贪心即可

// Author: xiaruize
const int N = 1e6 + 10;

int n;
int val[N];
int mi = INF;
int a[N], pos[N], b[N];
bool vis[N];

void solve()
{
	cin >> n;
	rep(i, 1, n)
	{
		cin >> val[i];
		mi = min(mi, val[i]);
	}
	rep(i, 1, n)
	{
		cin >> a[i];
		pos[a[i]] = i;
	}
	rep(i, 1, n) cin >> b[i];
	int res = 0;
	rep(i, 1, n)
	{
		if (!vis[i])
		{
			int x = i;
			int cnt = 0, sum = 0;
			int mn = INF;
			while (!vis[x])
			{
				vis[x] = true;
				sum += val[a[x]];
				mn = min(mn, val[a[x]]);
				cnt++;
				x = pos[b[x]];
			}
			res += sum + min(mn * (cnt - 2), mn + mi * (cnt + 1));
		}
	}
	cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}

标签：cnt,POI2009SLO,val,Elephants,int,mn,mi,vis
From： https://www.cnblogs.com/xiaruize/p/18142218