题目意思
\(有一个数列a，每次可以挑选任意两个元素交换位置，代价为这两个元素的和，问把序列a升序排序所需的最小总代价\)
\(定义数列上的一个有i个元素的环S使得s_1要换到s_2,s_2要到s_3,……,s_i要到s_1\)
\(原图一个元素只有一个目标位置，所以可以看作一个有n点,n边的有向图\)
\(对于在一个大小为m的环S上的点，可以每次拿最小值进行交换，总次数为m-1次，总代价为环上总值加上最小值的额外代价\)
\(即sum_S+minn_S*(num_S-2)\)
\(易证，对于环内的其他交换方式，此方式为最优\)
\(对于没有在大环中的点，实际上在一个只有一个点的自环中，此公式同样成立\)
\(但，交换不一定要在环内进行，如\)
\(5\)
\(1\ 8\ 9\ 7\ 6\)
\(若只在环内交换，显然答案为9+6+8+6+7+6=42\)
\(但是可以{1,6}/{1,9}/{1,7}/{1,8}/{1,6}五次交换\)
\(1,8,9,7,6\)
\(6,8,9,7,1\)
\(6,8,1,7,9\)
\(6,8,7,1,9\)
\(6,1,7,8,9\)
\(1,6,7,8,9\)
\(总代价为1*5+6+9+8+7+6\)
\(设minx为整个数组最小值,易得公式为 minx*(num_S+1)+minn_S+sum_S\)
\(于是对于每个环，答案为min(sum_S+minn_S*(num_S-2),minx*(num_S+1)+minn_S+sum_S)\)
\(求环有很多方法，我这里用的tarjan\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,dfn[100009],low[100009],v[100009],cnt,cols,col[100009],q[100009],top;
struct dian
{
int x,nd,v;
}a[100009];
bool cmp1(dian i,dian j)
{
return i.v<j.v;
}
bool cmp2(dian i,dian j)
{
return i.x<j.x;
}
int minn[100009],num[100009],sum[100009],ans;
void tarjan(int x)
{
cnt++;
dfn[x]=low[x]=cnt;
q[++top]=x;
v[x]=1;
if(dfn[a[x].nd]==0)
{
tarjan(a[x].nd);
low[x]=min(low[x],low[a[x].nd]);
}
else
if(v[a[x].nd]==1)
low[x]=min(low[x],dfn[a[x].nd]);
if(low[x]==dfn[x])
{
cols++;
int now;
do
{
now=q[top];
top--;
col[now]=cols;
minn[cols]=min(minn[cols],a[now].v);
sum[cols]+=a[now].v;
num[cols]++;
}while(dfn[now]!=dfn[x]);
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
minn[i]=1e9+7;
cin>>a[i].v;
a[i].x=i;
}
sort(a+1,a+n+1,cmp1);
int minx=a[1].v;
for(int i=1;i<=n;i++)
{
a[i].nd=i;
}
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++)
if(dfn[i]==0)
tarjan(i);
for(int i=1;i<=cols;i++)
{
ans+=min(minn[i]*(num[i]-2)+sum[i],minx*(num[i]+1)+sum[i]+minn[i]);
}
cout<<ans;
return 0;
}