【违规紫衫】关于最小成本排序

在阅读《挑战程序设计竞赛2》中有一题（P143），其大致为给定一些货物的重量，每次可以调换两个货物，成本为

w[i] + w[j]

（其中

i

j

为所调换的两个货物，

w

是货物的重量），问求按升序排序时所需最小成本是多少？（详细题目可以去这)

在书中，它的做法是找要调换的“圆”，即每个点要到达它自己位子所交换所组成的“圆”，一个就是在这个圆中用最小的值不停调换，公式为

\Sigma w[i] + (n - 2) * min(w[i])

，还有一种就是从所有数中找最小的来调换，公式为

\Sigma w[i] + min(w[i]) + (n + 1) * x

（

x

为所有数中最小值），然后代码如下：（这是我自己打的，如果看不惯可以去看看网上的，都是书上的）

CPP

//
#define debug
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e3 + 1, Maxm = 1e4 + 1;
int n, ans, a[Maxn], s, b[Maxn], t[Maxm]; 
bool f[Maxn];

void dfs(){	//函数没啥别的意思时就喜欢叫dfs，跟深搜没半毛钱关系 
	ans = 0;
	memset(f, 0, sizeof(f));
	for(int i = 1; i <= n; i++){
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	for(int i = 1; i <= n; i++){
		t[b[i]] = i;
	}
	for(int i = 1; i <= n; i++){
		if(f[i]){
			continue;
		}
		int tmp, qwq = i, S = 0, m = Maxm, cnt = 0;
		while(1){
			f[qwq] = true;
			cnt++;
			tmp = a[qwq];
			m = min(m, tmp);
			S += tmp;
			qwq = t[tmp];
			if(f[qwq]){
				break;
			}
		}
		ans += min(S + (cnt - 2) * m, m + S + (cnt + 1) * s);
	}
}

int main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  s = Maxm;
  for(int i = 1; i <= n; i++){
  	cin >> a[i];
  	s = min(a[i], s);
	}
	dfs();
	cout << ans << endl;
	return 0;
}

其中在代码

18

36

行中间那段代码不是很懂，有大佬帮忙看一下吗qwq，万分感谢

【违规紫衫】关于最小成本排序

讨论操作

回复

相关推荐

【违规紫衫】关于最小成本排序