USACO3.2.6Sweet Butter

Sweet Butter

Greg Galperin -- 2001

Farmer John has discovered the secret to making the sweetest butter in all of Wisconsin: sugar. By placing a sugar cube out in the pastures, he knows the N (1 <= N <= 500) cows will lick it and thus will produce super-sweet butter which can be marketed at better prices. Of course, he spends the extra money on luxuries for the cows.

FJ is a sly farmer. Like Pavlov of old, he knows he can train the cows to go to a certain pasture when they hear a bell. He intends to put the sugar there and then ring the bell in the middle of the afternoon so that the evening's milking produces perfect milk.

FJ knows each cow spends her time in a given pasture (not necessarily alone). Given the pasture location of the cows and a description of the paths the connect the pastures, find the pasture in which to place the sugar cube so that the total distance walked by the cows when FJ rings the bell is minimized. FJ knows the fields are connected well enough that some solution is always possible.

PROGRAM NAME: butter

INPUT FORMAT

Line 1: Three space-separated integers: N, the number of pastures: P (2 <= P <= 800), and the number of connecting paths: C (1 <= C <= 1,450). Cows are uniquely numbered 1..N. Pastures are uniquely numbered 1..P.
Lines 2..N+1: Each line contains a single integer that is the pasture number in which a cow is grazing. Cow i's pasture is listed on line i+1.
Lines N+2..N+C+1: Each line contains three space-separated integers that describe a single path that connects a pair of pastures and its length. Paths may be traversed in either direction. No pair of pastures is directly connected by more than one path. The first two integers are in the range 1..P; the third integer is in the range (1..225).

SAMPLE INPUT (file butter.in)

INPUT DETAILS

This diagram shows the connections geometrically:

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

OUTPUT FORMAT

Line 1: A single integer that is the minimum distance the cows must walk to a pasture with a sugar cube.

SAMPLE OUTPUT (file butter.out)

8

OUTPUT DETAILS:

Putting the cube in pasture 4 means: cow 1 walks 3 units; cow 2 walks 5
units; cow 3 walks 0 units -- a total of 8.

题解：很明显是最短路问题，我用的是SPFA，对每个牧场SPFA一下，然后计算每头牛到放糖的那个牧场的距离的和并与最短距离比较。如果小，则更新，要注意一个牧场有多头牛的情况，我就被这个坑了。。。我用的就是普通的邻接矩阵，第八个测试点是0.9s。。第九个点就超时了。。。因为此题是个稀疏图，节点N=800，边数edg=1450。在松弛操作的时候如果是枚举每一个点的话，效率非常的低，所以我们要用邻接表存储图。在松弛操作的时候只要枚举与当前出队的元素直接相连的节点即可。这样的话大大减少了无效操作。下面是用静态邻接表优化之后的评测时间。

   Test 1: TEST OK [0.000 secs, 6340 KB]
   Test 2: TEST OK [0.000 secs, 6340 KB]
   Test 3: TEST OK [0.000 secs, 6340 KB]
   Test 4: TEST OK [0.000 secs, 6340 KB]
   Test 5: TEST OK [0.000 secs, 6340 KB]
   Test 6: TEST OK [0.000 secs, 6340 KB]
   Test 7: TEST OK [0.032 secs, 6340 KB]
   Test 8: TEST OK [0.065 secs, 6340 KB]
   Test 9: TEST OK [0.119 secs, 6340 KB]
   Test 10: TEST OK [0.119 secs, 6340 KB]
以后在做图论题时，要认真看清楚题目条件，然后再选取相应的存储方式存储图。

View Code

 1 /*
 2 ID:spcjv51
 3 PROG:butter
 4 LANG:C
 5 */
 6 #include<stdio.h>
 7 #include<string.h>
 8 #define MAXS 10000000
 9 long d[1000];
10 int f[1000],visit[1000];
11 int graph[1000][1000];
12 int lj[1000][105];
13 int n,p,c;
14 long minpath;
15 void SPFA(int s)
16 {
17     int i,head,tail,t;
18     int q[3000];
19     memset(visit,0,sizeof(visit));
20     memset(q,0,sizeof(q));
21     for(i=1; i<=p; i++)
22         d[i]=MAXS;
23     d[s]=0;
24     head=0;
25     tail=1;
26     q[1]=s;
27     visit[s]=1;
28     while(head<tail)
29     {
30         head++;
31         t=q[head];
32         visit[t]=0;
33         for(i=1; i<=lj[t][0]; i++)
34             if(d[t]+graph[t][lj[t][i]]<d[lj[t][i]])
35             {
36                 d[lj[t][i]]=d[t]+graph[t][lj[t][i]];
37                 if(!visit[lj[t][i]])
38                 {
39                         tail++;
40                         q[tail]=lj[t][i];
41                         visit[lj[t][i]]=1;
42                 }
43             }
44     }
45 }
46 int main(void)
47 {
48     freopen("butter.in","r",stdin);
49     freopen("butter.out","w",stdout);
50     int i,j,x,y,z;
51     long ans;
52     scanf("%d%d%d",&n,&p,&c);
53     for(i=1; i<=n; i++)
54         scanf("%d",&f[i]);
55         memset(lj,0,sizeof(lj));
56     for(i=0;i<=p;i++)
57     for(j=0;j<=p;j++)
58     graph[i][j]=MAXS;
59     for(i=1; i<=c; i++)
60     {
61         scanf("%d%d%d",&x,&y,&z);
62         graph[x][y]=z;
63         graph[y][x]=z;
64         lj[x][0]++;
65         lj[x][lj[x][0]]=y;
66         lj[y][0]++;
67         lj[y][lj[y][0]]=x;
68     }
69 
70     minpath=MAXS;
71     for(i=1; i<=p; i++)
72     {
73         ans=0;
74         SPFA(i);
75         for(j=1; j<=n; j++)
76             ans+=d[f[j]];
77         if(ans<minpath) minpath=ans;
78 
79     }
80     printf("%ld\n",minpath);
81     return 0;
82 
83 }