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)
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
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.
题意：
给出农场的地图，以及哪些农区上有牛。农民在农区上放快butter。求所有牛到butter的距离之和最小值。
代码如下：
bellman：
/*
LANG: C
TASK: butter
*/
#include<stdio.h>
#define maxn 801
#define inf 100000000
int Edge[1450][3], dis[maxn], t[maxn];
void set(int f, int n)
{
int i;
for (i = 1; i <= n; i++)
{
dis[i] = inf;
}
dis[f] = 0;
}
int relax(int th)
{
int u = Edge[th][0], v = Edge[th][1], w = Edge[th][2], sign = 0;
if (dis[u] > dis[v] + w)
{
dis[u] = dis[v] + w;
sign = 1;
}
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
sign = 1;
}
return sign;
}
void bellman(int f, int n, int edgeNum)
{
int i, j, sign;
set(f, n);
for (i = 1; i < n; i++)
{
for (j = 0, sign = 0; j < edgeNum; j++)
{
if (relax(j))
{
sign = 1;
}
}
if (!sign)
{
break;
}
}
}
void find(m, n, edgeNum)
{
int i, j, pre, sum;
for (i = 1, pre = inf; i <= n; i++)
{
bellman(i, n, edgeNum);
for (j = 0, sum = 0; j < m; j++)
{
sum += dis[t[j]];
}
if (pre > sum)
{
pre = sum;
}
}
printf("%d\n", pre);
}
void read()
{
int i, n, u, v, m, w, edgeNum;
scanf("%d%d%d", &m, &n, &edgeNum);
for (i = 0; i < m; i++)
{
scanf("%d", &t[i]);
}
for (i = 0; i < edgeNum; i++)
{
scanf("%d%d%d", &u, &v, &w);
Edge[i][0] = u, Edge[i][1] = v, Edge[i][2] = w;
}
find(m, n, edgeNum);
}
int main()
{
freopen("butter.in", "r", stdin), freopen("butter.out", "w", stdout);
read();
fclose(stdin), fclose(stdout);
//system("pause");
return 0;
}
spfa：
/*
LANG: C
TASK: butter
*/
#include<stdio.h>
#define maxn 801
#define inf 1 << 30
int t[maxn], len[maxn], dis[maxn], visit[maxn], queue[maxn * 3], nn[maxn], num = 0;
typedef struct node
{
int to, w;
}N;
N map[maxn][maxn];
void setLen(int n)
{
int i;
for (i = 1; i <= n; i++)
{
len[i] = 0;
}
}
void set(int s, int n)
{
int i;
for (i = 1; i <= n; i++)
{
dis[i] = inf, visit[i] = 0;
}
dis[s] = 0;
}
void add(int u, int v, int w)
{
map[u][len[u]].to = v, map[u][len[u]].w = w, len[u]++;
map[v][len[v]].to = u, map[v][len[v]].w = w, len[v]++;
}
void spfa(int s, int n)
{
int i, head = 0, tial = 1, pre, j, v, w, relax;
set(s, n);
queue[head] = s;visit[s] = 1;
while (head != tial)
{
pre = queue[head++], visit[pre] = 0;
for (j = 0; j < len[pre]; j++)
{
v = map[pre][j].to, w = map[pre][j].w;
relax = dis[pre] + w;
if (dis[v] > relax)
{
dis[v] = relax;
if (!visit[v])
{
visit[v] = 1;
queue[tial++] = v;
}
}
}
}
//for (i = 1; i <= n; i++)printf("%d ", dis[i]);
}
void find(int h, int n)
{
int i, j, min, pre;
for (i = 1, min = inf; i <= n; i++)
{
spfa(i, n);
for (j = 0, pre = 0; j < num; j++)
{
pre += dis[nn[j]] * t[nn[j]];
}
if (min > pre)
{
min = pre;
}
}
printf("%d\n", min);
}
void read()
{
int h, n, m, i, j, u, v, w, f;
scanf("%d%d%d", &h, &n, &m);
setLen(n);
for (i = 0; i < h; i++)
{
scanf("%d", &f);
if (t[f])
{
t[f]++;
}
else
{
t[f]++;
nn[num++] = f;
}
}
for (i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
find(h, n);
}
int main()
{
freopen("butter.in", "r", stdin), freopen("butter.out", "w", stdout);
read();
fclose(stdin), fclose(stdout);
//system("pause");
return 0;
}