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; } |