**Theory:**

The key to figuring out this problem was to recognize that you needed to resolve cycles in the data –

if you follow an item to the item that’s in its spot, and then the one that’s in the next one’s spot, until you

reach the original item again, you’ll have a cycle of elements that should be in each others’ spots. If an item

is already in its spot, it forms a cycle of one element. The minimum cost of resolving a cycle is (sum of the

weights in the cycle)+(number of elements in the cycle-2)*(minimum weight in cycle). This cost is zero for

one-element cycles and the sum of the elements for two-element cycles. For larger cycles, it is the cost of

swapping the smallest element in the cycle with each element until all of them are in the right spot.

The tricky part of this problem is figuring out that simply resolving all the cycles doesn’t always give you the

best answer. Sometimes the optimal answer comes by swapping the smallest element of the whole set into the cycle

and then resolving the new cycle. The cost of swapping in the smallest element is the sum of that weight and the

smallest weight in the cycle. The cost of resolving the new cycle is (sum of the weights in the cycle + minimum

of all weights) + (number of elements in the cycle + 1) * (minimum of all weights). Sometimes this creates a

smaller final value and sometimes it makes it bigger. The key to this problem was figuring out which cycles

should merge with the smallest element and which should just be resolved.

[highlight]**minimum of (sum of the weights in the cycle)+(number of elements in the cycle-2)*(minimum weight in cycle)**

**2*(minimum_of_all_weights + minimum_weight_cycle) + (sum_of_weights_in_cycle – minimum_weight_cycle)**

**+(number of elements in the cycle -1)* minimum_of_all_weights**[/highlight]

**Solution:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include <iostream> #include <algorithm> #include <vector> #include <map> #define lld long long using namespace std; int a[1001]; int b[1001]; int min_valu_cycle[1001]; map<int,int> visit; vector<int> v[1001]; int position[1001]; int main() { int n,cycle_min,_min; bool flag = true; lld total_cycle_weight,total; int cnt,kase=1; while(cin>>n) { cnt=0; total=0; if(n==0) break; for(int i=0;i<n;i++) { cin>>a[i]; b[i]=a[i]; v[i].clear(); position[i]=0; } for(int i=n;i<1001;i++) { position[i]=0; v[i].clear(); } visit.clear(); sort(b,b+n); _min = b[0]; for(int i=0;i<n;i++) { position[b[i]]=i; } for(int i=0;i<n;i++) { if(visit[i]) continue; total_cycle_weight=0; visit[i]=1; v[cnt].push_back(a[i]); total_cycle_weight+=a[i]; cycle_min = a[i]; int next = position[a[i]]; while(!visit[next]) { visit[next]=1; total_cycle_weight+=a[next]; v[cnt].push_back(a[next]); if(a[next]<cycle_min) cycle_min=a[next]; next = position[a[next]]; } total_cycle_weight -= cycle_min; total+= total_cycle_weight + cycle_min * (v[cnt].size()-1); if(2*(cycle_min+b[0]) < ((v[cnt].size()-1) * (cycle_min-b[0]))) total -= (((v[cnt].size()-1) * (cycle_min-b[0])) - 2*(cycle_min+b[0])); //total_cycle_weight+_min+((v[cnt].size()+1)*_min); // cnt++; } cout<<"Case "<<kase++<<": "; cout<<total<<"\n\n"; } return 0; } |