pc网站建设怎么样,如何做好外贸网络营销,骨干专业建设网站,网站排名优化是怎么做的有几个错误#xff0c;调试了几个小时#xff0c;样例过后 1Y. 题目#xff1a;http://poj.org/problem?id3026 题意#xff1a;就是让求A们和S的最小生成树 先用bfs找每两点的距离#xff0c;再建树。没剪枝 63MS。 1 #include iostream2 #includecstdio调试了几个小时样例过后 1Y. 题目http://poj.org/problem?id3026 题意就是让求A们和S的最小生成树 先用bfs找每两点的距离再建树。没剪枝 63MS。 1 #include iostream2 #includecstdio3 #includecstring4 #includecstdlib5 #includestack6 #includequeue7 #includecmath8 #includealgorithm9 using namespace std;10 11 char G[60][60];12 int dx[5]{0,0,1,-1};13 int dy[5]{1,-1,0,0};14 int r,c,bin[10010],an,ff[150][150]; //an表示边数15 struct node16 {17 int x,y;18 }e[150]; //表示点19 20 struct tree21 {22 int u,v,w;23 }q[11000];//边及权值24 25 struct point26 {27 int x,y,step;28 }next,pos;//bfs 里的队列29 30 void add(int u,int v,int w)//加边31 {32 q[an].uu; q[an].vv; q[an].ww;33 }34 35 void bfs(int f,int x,int y)36 {37 int vis[60][60],i;38 queuepointqu;39 memset(vis,0,sizeof(vis));40 next.xx; next.yy; next.step0;41 qu.push(next);42 vis[x][y]1;43 while(!qu.empty())44 {45 posqu.front();46 qu.pop();47 for(i0; i4; i)48 {49 next.xpos.xdx[i]; next.ypos.ydy[i]; next.steppos.step1;50 if(next.x0 next.xr next.y0 next.yc vis[next.x][next.y]0 G[next.x][next.y]!#)51 {52 vis[next.x][next.y]1;53 qu.push(next);54 if(G[next.x][next.y]A||G[next.x][next.y]S)55 add(f,ff[next.x][next.y],next.step);56 }57 }58 }59 }60 int cmp(const void *a,const void *b)61 {62 return (*(tree *)a).w-(*(tree *)b).w;63 }64 int find(int a)65 {66 if(abin[a])67 return a;68 else69 bin[a]find(bin[a]);70 };71 int main()72 {73 int t,cnt,i,j,x,y,num,sum;//cnt表示点的个数74 char str[200];75 cint;76 while(t--)77 {78 sum0; num0; an0;79 cincr;80 gets(str);81 for(i0; ir; i)82 gets(G[i]);83 84 cnt0;85 for(i0; ir; i)86 for(j0; jc; j)87 if(G[i][j]S||G[i][j]A)88 {89 ff[i][j]cnt;90 e[cnt].xi; e[cnt].yj;91 }92 93 for(i0; icnt; i)94 {95 bfs(i,e[i].x,e[i].y);96 }97 98 for(i0; icnt; i)99 bin[i]i;
100 qsort(q,an,sizeof(q[0]),cmp);
101 for(i0; ian-1; i)
102 {
103 xfind(q[i].u); yfind(q[i].v);
104 if(x!y)
105 {
106 sumq[i].w;
107 num;
108 bin[x]y;
109 }
110 if(numcnt-1)
111 break;
112 }
113 printf(%d\n,sum);
114 }
115 }
116 转载于:https://www.cnblogs.com/bfshm/p/3253262.html
