Sweet Butter
Greg Galperin -- 2001Farmer 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.
题意:
给出 N 头牛,P 个棚, M 条双向路,后给出 N 头牛所在的棚是哪个,和 M 条棚与棚之间的路。现要找到一个牛棚,使所有牛到达这个棚的总和值最小。
思路:
最短路。Floyd 会卡时间,所以用 Dijkstra 算出每个棚的最短路后,每个棚的距离再乘以当前棚中牛的个数的总和值,同时比较大小即可。
AC:
/* ID:sum-g1 LANG:C++ PROG:butter */ #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <utility> using namespace std; typedef pair<int, int> pii; const int INF = 999999999; const int VMAX = 805; const int EMAX = 1455 * 2; int cnt[805], p; int fir[VMAX], next[EMAX], v[EMAX], w[EMAX]; int ind; int d[VMAX]; bool vis[VMAX]; void init () { memset(cnt, 0, sizeof(cnt)); memset(fir, -1, sizeof(fir)); ind = 0; } void add_edge(int f, int t, int val) { v[ind] = t; w[ind] = val; next[ind] = fir[f]; fir[f] = ind; ++ind; } void Dijstra (int a) { for (int i = 1; i <= p; ++i) d[i] = i == a ? 0 : INF; memset(vis, 0, sizeof(vis)); priority_queue<pii, vector<pii>, greater<pii> > q; q.push(make_pair(d[a], a)); while (!q.empty()) { pii t = q.top(); q.pop(); int x = t.second; if (vis[x]) continue; vis[x] = 1; for (int e = fir[x]; e != -1; e = next[e]) { int y = v[e]; if (d[y] > w[e] + d[x]) { d[y] = w[e] + d[x]; q.push(make_pair(d[y], y)); } } } } int main() { freopen("butter.in","r",stdin); freopen("butter.out","w",stdout); int n, c; scanf("%d%d%d", &n, &p, &c); init(); while (n--) { int ans; scanf("%d", &ans); ++cnt[ans]; } while (c--) { int a, b, w; scanf("%d%d%d", &a, &b, &w); add_edge(a, b, w); add_edge(b, a, w); } int Min_dis = INF; for (int i = 1; i <= p; ++i) { Dijstra(i); int sum = 0; for (int j = 1; j <= p; ++j) { sum += d[j] * cnt[j]; if (sum >= Min_dis) break; } Min_dis = min(Min_dis, sum); } printf("%d\n", Min_dis); return 0; }
相关推荐
USACO的第三章的题目sweet buter的代码,已经通过code blocks编译
C语言实现python的butter函数,自测可用。已经在商用产品中使用了。
用C语言实现matlab的butter函数中低通和带通功能,高通和带阻没写,有兴趣的可以自己加入.
butterfly behaviour for data sending & receiving
butter滤波器matlab实现,里面具体参数根据自己调
代码验证请看我的博客: http://blog.csdn.net/zone53/article/details/78280901
matlab butter()函数解析。 一篇文章带你快速了解!
巴特沃斯滤 波器滤波 100Hz有直接型级联型并联型双线性
代码验证请看我的博客: http://blog.csdn.net/zone53/article/details/78280901
资源分类:Python库 所属语言:Python 资源全名:butter-0.9.zip 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
butter_c_butter_matlab.butter_matlabbutter_IIR数字滤波器的实现;.zip
butter_c_butter_matlab.butter_matlabbutter_IIR数字滤波器的实现;_源码
Google IO 2012大会上Chet Hase和Romain Guy做的主题演讲的ppt,介绍了Android绘图渲染的改进,以及如何调优渲染速度
matlab编写的巴特沃斯带通滤波器,对应于我的博文中的带通滤波器,需要的可以自行下载。它的参数分别为低频、高频、采样率、阶数。
MATLAB求巴特沃斯IIR滤波器,对比演示滤波效果, 采样率Fs=4000Hz,-3db通带截止频率80Hz,阻带截止频率200Hz.
Apple Butter
:eyes:在Twitter上关注我,以获取有关Butter Slider的最新消息: :butter: :butter: :butter: :butter: 安装 使用NPM或纱线 # With NPM npm i --save butter-slider # With Yarn yarn add butter-slider 带有CDN &...
快速移除Android 代码中 butterknife-zelezny 生成 ButterKnife 注解,并自动生成findViewById 代码