USACO 3.2.6 Sweet Butter 香甜的黄油 解题报告

这题一开始我用的那个O(n^3)的算法，叫什么名字我忘了，肯定是超时了咯，因为图是稀疏图，这样是肯定超时的，后来就看标称，看了好久，真没想到标称竟然如此精妙，里面设计了一个能够以O(1)的速度查找元素的功能，整个程序是执行了至多n次Dijkstra算法，然后我在里面增加了一些优化（几乎和时间无关的优化，因为数据量太大，CPU又太好用了），比如用位运算代替乘除法(乘以或除以2)，在上滤和下滤的过程把递归改成了非递归，防止重复的牛所在的牧场进行计算，让heap_val在上滤和下滤的过程中不修改，反正最大的数据程序还是要0.16s才能完成，不知道算不算快。
不过此代码是我写的可读性最低的代码之一，能读都就读吧。

/*
LANG: C
ID: zqynux2
PROG: butter
*/
#include <stdio.h>
const int INTMAX = 1<<30;

int heap_val[800];
int heap_id[800];
int heap_lookup[800];
int heap_size;
#define left(i) (((i) << 1) + 1)
#define right(i) (((i) << 1) + 2)
#define parent(i) ((i - 1) >> 1) 

void heapdown(int t)
{
 int i, ch;
 int id = heap_id[t];
 for(i = t; left(i) < heap_size; i = ch){
 ch = left(i);
 if(ch + 1 < heap_size && heap_val[heap_id[ch + 1]] <
 heap_val[heap_id[ch]]){
 ch++;
 }
 if(heap_val[id] > heap_val[heap_id[ch]]){
 heap_lookup[heap_id[ch]] = i;
 heap_id[i] = heap_id[ch];
 }else{
 break;
 }
 }
 heap_lookup[id] = i;
 heap_id[i] = id;
}

void heapup(int t)
{
 int i;
 int id = heap_id[t];
 for(i = t; i > 0 && heap_val[id]
 < heap_val[heap_id[parent(i)]]; i = parent(i)){
 heap_lookup[heap_id[parent(i)]] = i;
 heap_id[i] = heap_id[parent(i)];
 }
 heap_lookup[id] = i;
 heap_id[i] = id;
}

int cows[500];
int link[800][800];
int value[800][800];
int count[800];
int used[500];
int fixed[800];
int dist[800][800];
int n, p, c;

int main(void)
{
 int i, j, k;
 int t, s;
 freopen(butter.in, r, stdin);
 freopen(butter.out, w, stdout);
 scanf(%d%d%d, &n, &p, &c);
 for(i = 0; i < n; i++){
 scanf(%d, &cows[i]);
 cows[i]--; //掉了这一行代码 
 }
 {
 int a, b, d;
 for(i = 0; i < c; i++){
 scanf(%d%d%d, &a, &b, &d);
 a--, b--;
 link[a][count[a]] = b;
 link[b][count[b]] = a;
 value[a][count[a]] = value[b][count[b]] = d;
 count[a]++, count[b]++;
 }
 }
 for(i = 0; i < n; i++){
 if(used[i]){
 continue;
 }
 used[i] = 1;
 heap_size = p;
 for(j = 0; j < p; j++){
 heap_id[j] = j;
 heap_val[j] = INTMAX;
 heap_lookup[j] = j;
 }
 heap_val[cows[i]] = 0;
 heapup(cows[i]);
 memset(fixed, 0, sizeof(fixed));
 while(heap_size != 0){
 t = heap_id[0];
 dist[cows[i]][t] = heap_val[t];
 fixed[t] = 1;
 heap_size--;
 heap_lookup[heap_id[heap_size]] = 0;
 heap_id[0] = heap_id[heap_size];
 heapdown(0);
 for(k = 0; k < count[t]; k++){
 s = link[t][k];
 if(!fixed[s] && heap_val[s] > heap_val[t] + value[t][k]){
 heap_val[s] = heap_val[t] + value[t][k];
 heapup(heap_lookup[s]);
 }
 }
 }
 }
 {
 int ans = INTMAX, tmp;
 for(i = 0; i < p; i++){
 tmp = 0;
 for(j = 0; j < n; j++){
 tmp += dist[cows[j]][i];
 }
 if(ans > tmp){
 ans = tmp;
 }
 }
 printf(%d\\n, ans);
 }
 return 0;
}