Ship Cargo
National Olympiad — National round
Submission name: ship.cpp
Problem summary
Item i starts at position i, with positions numbered from 0. It weighs T[i] and must finish at position P[i]. Swapping two items costs the sum of their weights. Minimize the total cost of placing every item at its prescribed destination; equal weights do not make items interchangeable.
Input
N, then N weights T, then N distinct destination positions P.
Output
The minimum total swapping cost.
Constraints
2 ≤ N ≤ 10,000; 1 ≤ T[i] ≤ 100,000; 0 ≤ P[i] < N.
Worked example
An independently prepared example for this explanation.
Input
3 5 2 4 1 2 0
Output
13
Solution analysis
- Split the destination permutation into cycles.
- For a nontrivial cycle of length k, total weight S and minimum m, using its lightest item as helper costs S+(k−2)m.
- Alternatively borrow the globally lightest item g and return it afterward, costing S+m+(k+1)g.
- Sum the cheaper choice for every cycle.
Why it works
With an internal helper, all other cycle items must move and the cheapest cycle weight is used k−1 times. An external helper needs an import and return in addition to processing the cycle, giving the second formula. More expensive helpers or additional transfers cannot lower either necessary cost. A borrowed helper is restored, so the cycle costs can be combined.
Watch out. Destinations are prescribed, not obtained by sorting weights. Use 64-bit totals.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<long long>w(n);
for(auto&x:w){
cin>>x;
}
vector<int>p(n);
for(int&x:p){
cin>>x;
}
long long g=*min_element(w.begin(),w.end()),answer=0;
vector<bool>seen(n);
for(int s=0;s<n;s++){
if(!seen[s]){
long long sum=0,m=numeric_limits<long long>::max();
int k=0;
for(int v=s;!seen[v];v=p[v]){
seen[v]=true;
sum+=w[v];
m=min(m,w[v]);
k++;
}
if(k>1){
answer+=min(sum+(k-2)*m,sum+m+(k+1)*g); // Compare both helpers.
}
}
}
cout<<answer<<'\n';
}