Sweet Butter Greg Galperin — 2001
Farmer John has discovered the secret to making the sweetest butterin all of Wisconsin: sugar. By placing a sugar cube out in thepastures, he knows the N (1 <= N <= 500) cows will lick it and thuswill produce super-sweet butter which can be marketed at betterprices. Of course, he spends the extra money on luxuries for thecows.
FJ is a sly farmer. Like Pavlov of old, he knows he can train thecows to go to a certain pasture when they hear a bell. He intends toput the sugar there and then ring the bell in the middle of theafternoon so that the evening’s milking produces perfect milk.
FJ knows each cow spends her time in a given pasture (not necessarilyalone). Given the pasture location of the cows and a description ofthe paths that connect the pastures, find the pasture in which to placethe sugar cube so that the total distance walked by the cows when FJrings the bell is minimized. FJ knows the fields are connected well enoughthat some solution is always possible.
PROGRAM NAME: butterINPUT FORMATSAMPLE INPUT (file butter.in)3 4 52341 2 11 3 52 3 72 4 33 4 5INPUT DETAILSThis diagram shows the connections geometrically:P2 P1 @–1–@ C1\ |\\ | \5 7 3\ | \\| \ C3C2 @–5–@P3 P4OUTPUT FORMAT Line 1: A single integer that is the minimum distance the cows must walk toa pasture with a sugar cube.SAMPLE OUTPUT (file butter.out) 8OUTPUT DETAILS:Putting the cube in pasture 4 means: cow 1 walks 3 units; cow 2 walks 5units; cow 3 walks 0 units — a total of 8.分析用邻接表存储路径，再用Dijkstra求出每个牧场作为中心的和，同时用小顶堆优化。我终于吃到你了，香甜的黄油。运行结果Executing… Test 1: TEST OK [0.008 secs, 3512 KB] Test 2: TEST OK [0.008 secs, 3512 KB] Test 3: TEST OK [0.003 secs, 3512 KB] Test 4: TEST OK [0.008 secs, 3512 KB] Test 5: TEST OK [0.016 secs, 3512 KB] Test 6: TEST OK [0.032 secs, 3512 KB] Test 7: TEST OK [0.068 secs, 3512 KB] Test 8: TEST OK [0.111 secs, 3512 KB] Test 9: TEST OK [0.186 secs, 3512 KB] Test 10: TEST OK [0.205 secs, 3512 KB]All tests OK.
通过代码/*ID: c1033311LANG: C++TASK: butter*/#include<stdio.h>#include<stdlib.h>//#include<string.h> //一定要注释掉才能通过编译#define MAX 0x7FFFFFFF/******************* 单链表中的元素 *******************/struct Node{int pp;int ww;struct Node *next; };/******************* 堆中元素（小顶堆，，下标从1开始）*******************/struct{int p;int w;}heap[801];int sum; //堆中元素的数量和int index[802]; //index[i]为牧场i在堆中的下标/******************* 初始化堆 *******************/void init_heap(int n,int start){ //n为牧场总数，start为开始牧场，它不在堆中int i,j;for(i=1,j=1;i<=n+1;++i)if(i!=start){heap[j].p=i;heap[j].w=MAX;index[i]=j;++j;}heap[j].p=start;heap[j].w=0;index[start]=j;sum=n-1;}/******************* 交换堆中下标为i,j的两个元素 *******************/void exchange_heap(int i,int j){int t,dt;index[heap[i].p]=j;index[heap[j].p]=i;t=heap[i].p;dt=heap[i].w;heap[i].p=heap[j].p;heap[i].w=heap[j].w;heap[j].p=t;heap[j].w=dt;}/******************* 上浮 *******************/void up_heap(int i,int dis){ //i牧场的距离减小到disint n=index[i];while((n/2)>=1 && dis<heap[n/2].w) //上浮{heap[n].w=heap[n/2].w;heap[n].p=heap[n/2].p;index[heap[n/2].p]=n;n/=2;}heap[n].w=dis; //插入heap[n].p=i;index[i]=n;}/******************* 下沉 *******************/void down_heap(int i,int dis){ //i牧场的距离增大到disint n=index[i];int m;while((2*n<=sum) && (dis>heap[2*n].w || dis>heap[2*n+1].w)) //下沉，堆最后有个虚拟牧场避免越界{m=heap[2*n].w<heap[2*n+1].w?2*n:2*n+1;heap[n].w=heap[m].w;heap[n].p=heap[m].p;index[heap[m].p]=n;n=m;}heap[n].w=dis; //插入heap[n].p=i;index[i]=n;}int main(){FILE *fin=fopen("butter.in","r");FILE *fout=fopen("butter.out","w");int N,P,C;struct Node *E[801]={NULL}; //从1开始int min_sum=MAX,temp; //从一点出发到其它点的和int cow[500];int i,j,a,b,c;fscanf(fin,"%d%d%d",&N,&P,&C);for(i=0;i<N;++i)fscanf(fin,"%d",&cow[i]);for(i=0;i<C;++i) //建立单链表{fscanf(fin,"%d%d%d",&a,&b,&c);struct Node *node=(Node*)malloc(sizeof(Node));node->pp=b;node->ww=c;node->next=E[a]; //头插法E[a]=node;node=(Node*)malloc(sizeof(Node));node->pp=a;node->ww=c;node->next=E[b]; //头插法E[b]=node;}for(i=1;i<=P;++i) //枚举所有的牧场作为中心点{int now=i;init_heap(P,now);for(j=1;j<P;++j) //更新牧场i到其它P-1个牧场的距离{Node *e=E[now];while(e!=NULL){if(index[e->pp]<=sum && heap[index[e->pp]].w>heap[index[now]].w+e->ww)up_heap(e->pp,heap[index[now]].w+e->ww);e=e->next;}//end whilenow=heap[1].p;exchange_heap(1,sum);exchange_heap(sum,sum+1);–sum; //删除当前距离最小的牧场down_heap(heap[1].p,heap[1].w);}temp=0;for(j=0;j<N;++j)temp+=heap[index[cow[j]]].w;if(temp<min_sum)min_sum=temp;}fprintf(fout,"%d\n",min_sum);return 0;}如果
不注释掉#include<string.h>的话，会出现以下情况。因为index[]和string.h中的一个函数声明冲突，真见鬼。详情请看《C专家编程》5.4警惕Interpositioning（P102）
伟人所达到并保持着的高处，并不是一飞就到的，
