代码
比这篇新的文章:
ratios.pas
比这篇旧的文章: range.right.cpp
作者: xpycc, 点击215次, 评论(0), 收藏者(0)
打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: range.right.cpp
butter.cpp
语言: C++, 标签: 无 2008/08/22发布 3个月前更新作者: xpycc, 点击215次, 评论(0), 收藏者(0)
C++语言: butter.cpp
01 /*
02 ID:xpycc1
03 PROG:butter
04 LANG:C++
05 */
06
07 #include <fstream>
08 #define MAXP 800
09 #define MAXN 500
10 using namespace std;
11
12 ifstream fin("butter.in");
13 ofstream fout("butter.out");
14
15 unsigned int n,p,c,path[MAXP+1][MAXP+1],dist[MAXP+1],scor[MAXN],
16 cont[MAXP+1][MAXP+1],heap[MAXP+1],len,hash[MAXP+1];
17 bool isin[MAXP+1];
18
19 //以下的两个过程都是偷懒，从HumbleNumbles的那道题目的humble.pas里搬过来的，再用C++重写
20 void sift1(unsigned int x,unsigned pos){ //上滤
21 unsigned int i,j; //i parent; j son
22 j=pos?pos:++len; i=j/2;
23 /*
24 *本来是直接写成j=pos;的，
25 *然后第一次进堆的东东自己在外面写++len这么一条；
26 *后来注意到第一次没有在堆中的点hash的值是0，
27 *要进堆的话还是从后面插入
28 *于是统一一下，就变成这个样子了
29 */
30 while(i>0 && dist[x]<dist[heap[i]]){
31 heap[j]=heap[i];
32 hash[heap[j]]=j;
33 j/=2; i/=2;
34 }
35 heap[j]=x; hash[x]=j;
36 }
37
38 void sift(){ //下滤
39 unsigned int i,j,t;
40 i=1; j=i*2; t=heap[i];
41 while(j<=len){
42 if(j<len && dist[heap[j]]>dist[heap[j+1]]) ++j;
43 if(dist[t]>=dist[heap[j]]){
44 heap[i]=heap[j];
45 hash[heap[i]]=i;
46 i=j; j=i*2;
47 }else break;
48 }
49 heap[i]=t; hash[t]=i;
50 }
51
52 int main(){
53 unsigned int i,j,a,b,w,m,mm,u;
54 fin>>n>>p>>c;
55 for(i=0;i<n;++i)
56 fin>>scor[i];
57 for(i=0;i<c;++i){
58 fin>>a>>b>>w;
59 path[a][++cont[a][0]]=path[b][++cont[b][0]]=w;
60 cont[a][cont[a][0]]=b;
61 cont[b][cont[b][0]]=a;
62 }
63 m=0xFFFFFFFF;
64 for(i=1;i<=p;++i){
65 len=0;
66 //初始化，没办法，就是这么烦
67 memset(isin,false,sizeof(isin)); isin[i]=true;
68 memset(heap,0,sizeof(heap));
69 memset(hash,0,sizeof(hash));
70 memset(dist,255,sizeof(dist)); dist[i]=0;
71 for(j=1;j<=cont[i][0];++j){
72 dist[cont[i][j]]=path[i][j];
73 sift1(cont[i][j],0); //从后面加入堆
74 }
75 while(len){
76 u=heap[1]; //hash[u]=0; 去掉的两句调试的时候看起来方便点
77 heap[1]=heap[len--]; //heap[len+1]=0;
78 hash[heap[1]]=1;
79 sift();
80 isin[u]=true;
81 //由于代码是移植过来的，所以原来的p就不能用了，否则一直错
82 for(j=1;j<=cont[u][0];++j)
83 if(!isin[cont[u][j]] && dist[cont[u][j]]>dist[u]+path[u][j]){
84 dist[cont[u][j]]=dist[u]+path[u][j];
85 sift1(cont[u][j],hash[cont[u][j]]);
86 //维护堆（修改或插入）
87 }
88 }
89 mm=0;
90 for(j=0;j<n;++j)
91 //MS给出的图都是连通的，不过增加程序健壮性所以加上
92 if(dist[scor[j]]==0xFFFFFFFF) continue;
93 else mm+=dist[scor[j]];
94 if(j==n && mm<m) m=mm;
95 }
96
97 fout<<m<<endl;
98 return 0;
99 }
02 ID:xpycc1
03 PROG:butter
04 LANG:C++
05 */
06
07 #include <fstream>
08 #define MAXP 800
09 #define MAXN 500
10 using namespace std;
11
12 ifstream fin("butter.in");
13 ofstream fout("butter.out");
14
15 unsigned int n,p,c,path[MAXP+1][MAXP+1],dist[MAXP+1],scor[MAXN],
16 cont[MAXP+1][MAXP+1],heap[MAXP+1],len,hash[MAXP+1];
17 bool isin[MAXP+1];
18
19 //以下的两个过程都是偷懒，从HumbleNumbles的那道题目的humble.pas里搬过来的，再用C++重写
20 void sift1(unsigned int x,unsigned pos){ //上滤
21 unsigned int i,j; //i parent; j son
22 j=pos?pos:++len; i=j/2;
23 /*
24 *本来是直接写成j=pos;的，
25 *然后第一次进堆的东东自己在外面写++len这么一条；
26 *后来注意到第一次没有在堆中的点hash的值是0，
27 *要进堆的话还是从后面插入
28 *于是统一一下，就变成这个样子了
29 */
30 while(i>0 && dist[x]<dist[heap[i]]){
31 heap[j]=heap[i];
32 hash[heap[j]]=j;
33 j/=2; i/=2;
34 }
35 heap[j]=x; hash[x]=j;
36 }
37
38 void sift(){ //下滤
39 unsigned int i,j,t;
40 i=1; j=i*2; t=heap[i];
41 while(j<=len){
42 if(j<len && dist[heap[j]]>dist[heap[j+1]]) ++j;
43 if(dist[t]>=dist[heap[j]]){
44 heap[i]=heap[j];
45 hash[heap[i]]=i;
46 i=j; j=i*2;
47 }else break;
48 }
49 heap[i]=t; hash[t]=i;
50 }
51
52 int main(){
53 unsigned int i,j,a,b,w,m,mm,u;
54 fin>>n>>p>>c;
55 for(i=0;i<n;++i)
56 fin>>scor[i];
57 for(i=0;i<c;++i){
58 fin>>a>>b>>w;
59 path[a][++cont[a][0]]=path[b][++cont[b][0]]=w;
60 cont[a][cont[a][0]]=b;
61 cont[b][cont[b][0]]=a;
62 }
63 m=0xFFFFFFFF;
64 for(i=1;i<=p;++i){
65 len=0;
66 //初始化，没办法，就是这么烦
67 memset(isin,false,sizeof(isin)); isin[i]=true;
68 memset(heap,0,sizeof(heap));
69 memset(hash,0,sizeof(hash));
70 memset(dist,255,sizeof(dist)); dist[i]=0;
71 for(j=1;j<=cont[i][0];++j){
72 dist[cont[i][j]]=path[i][j];
73 sift1(cont[i][j],0); //从后面加入堆
74 }
75 while(len){
76 u=heap[1]; //hash[u]=0; 去掉的两句调试的时候看起来方便点
77 heap[1]=heap[len--]; //heap[len+1]=0;
78 hash[heap[1]]=1;
79 sift();
80 isin[u]=true;
81 //由于代码是移植过来的，所以原来的p就不能用了，否则一直错
82 for(j=1;j<=cont[u][0];++j)
83 if(!isin[cont[u][j]] && dist[cont[u][j]]>dist[u]+path[u][j]){
84 dist[cont[u][j]]=dist[u]+path[u][j];
85 sift1(cont[u][j],hash[cont[u][j]]);
86 //维护堆（修改或插入）
87 }
88 }
89 mm=0;
90 for(j=0;j<n;++j)
91 //MS给出的图都是连通的，不过增加程序健壮性所以加上
92 if(dist[scor[j]]==0xFFFFFFFF) continue;
93 else mm+=dist[scor[j]];
94 if(j==n && mm<m) m=mm;
95 }
96
97 fout<<m<<endl;
98 return 0;
99 }
所有评论，共0条：( 我也来说两句)