poj-3026 N - bfs+最小生成树

╰半夏微凉° 2023-10-11 09:18 12阅读 0赞

题意：

一个迷宫，一堆外星人，从起点找到所有外星人，路径只能在有外星人的地方分叉，求最短总路径

最小生成树题，把每个外星人当做树的结点，对每个外星人分别bfs求到其他外星人的最短的路径，然后将这些路径用最小生成树求解，兵茶几的克尔苏卡尔用二维坐标转一维即可。这里数据量较小，所以可以直接用 x+y\*50 这样表示坐标。

毒瘤啊，长宽哪一行输入数据后面有一堆空格，会卡getline，不能只用一个个getchar()来吃掉长宽那一行的后面的回车

如果用getline读取，在读长宽后加一句 while(char c=getchar()!='\\n')c=getchar(); 即可。

AC代码如下：

1 #include<iostream>
      2 #include<cstdio>
      3 #include<queue>
      4 #include<algorithm>
      5 #include<cstring>
      6 //#define qqqq cout<<"Hello!"<<endl;
      7 using namespace std;
      8 typedef int sss;
      9 char g[550][550];
     10 bool info[550][550];
     11 sss T,n,m;
     12 sss tot,res,cnt,cnt2;
     13 
     14 
     15 
     16 sss tree[25500];
     17 sss uns(sss root){
     18     sss son=root;
     19     while(root!=tree[root])root=tree[root];
     20     while(son!=root){
     21         sss temp=tree[son];
     22         tree[son]=root;
     23         son=temp;
     24     }
     25     return root;
     26 }
     27 sss join(sss a,sss b){
     28     sss x=uns(a),y=uns(b);
     29     while(x!=y){
     30         tree[x]=y;
     31         tot++;
     32         return 1;
     33     }
     34     return 0;
     35 }
     36 
     37 struct e
     38 {
     39     sss x, y;
     40 };
     41 struct  edge{
     42     e from,to;sss len;
     43 }Edge[2000005];
     44 
     45 bool cmp(edge a,edge b){
     46     return a.len<b.len;
     47 }
     48 
     49 struct point{
     50     sss x,y,len;
     51 };
     52 void fuzhi(){
     53     for(int i=0;i<=n;i++){
     54         info[0][i]=0;
     55         info[i][0]=0;
     56     }
     57     for(sss i=1;i<=n;i++){
     58         for(sss j=1;j<=n;j++){
     59             if(g[i][j]==' ')info[i][j]=1;
     60             else if(g[i][j]=='A'||g[i][j]=='S')info[i][j]=1;
     61             else info[i][j]=0;
     62         }
     63     }
     64 }
     65 void bfs(e start){
     66     fuzhi();
     67     queue <point> qq;
     68     point ss;
     69     ss.x=start.x;ss.y=start.y;ss.len=0;
     70     qq.push(ss);
     71     while(!qq.empty()){
     72         point now=qq.front();qq.pop();
     73         if(info[now.x][now.y]==0)continue;
     74         e tpp;tpp.x=now.x;tpp.y=now.y;
     75         //cout<<now.x<<" "<<now.y<<" "<<info[now.x][now.y]<<endl;
     76         if(g[now.x][now.y]=='A'||g[now.x][now.y]=='S'){
     77             edge tppp;
     78             tppp.to=tpp;
     79             tppp.from=start;
     80             tppp.len=now.len;
     81             Edge[cnt2++]=tppp;
     82         }
     83         info[now.x][now.y]=0;
     84         if(info[now.x+1][now.y]==1){
     85             point tp;
     86             tp.x=now.x+1;tp.y=now.y;tp.len=now.len+1;
     87             qq.push(tp);
     88         }
     89         if(info[now.x][now.y+1]==1){
     90             point tp;
     91             tp.x=now.x;tp.y=now.y+1;tp.len=now.len+1;
     92             qq.push(tp);
     93         }
     94         if(info[now.x-1][now.y]==1){
     95             point tp;
     96             tp.x=now.x-1;tp.y=now.y;tp.len=now.len+1;
     97             qq.push(tp);
     98         }
     99         if(info[now.x][now.y-1]==1){
    100             point tp;
    101             tp.x=now.x;tp.y=now.y-1;tp.len=now.len+1;
    102             qq.push(tp);
    103         }
    104     }
    105 }
    106 void solve(){
    107     fuzhi();
    108     for(sss i=1;i<=n;i++){
    109         for(sss j=1;j<=n;j++){
    110             if(g[i][j]=='S'||g[i][j]=='A'){
    111 
    112                 e tp;
    113                 tp.x=i;tp.y=j;
    114                 bfs(tp);
    115                 cnt++;
    116             }
    117         }
    118     }
    119 }
    120 
    121 void kersukaer(){
    122     for(sss i=0;i<cnt2;i++){
    123         if(join((Edge[i].from.x+Edge[i].from.y*50),(Edge[i].to.x+Edge[i].to.y*50))){
    124             res+=Edge[i].len;
    125         }
    126     }
    127 }
    128 
    129 int main(){
    130     cin>>T;
    131     while(T--){
    132         for(sss i=0;i<25000;i++)tree[i]=i;
    133         memset(Edge,0,sizeof(Edge));
    134         memset(g,0,sizeof(g));
    135         memset(info,0,sizeof(info));
    136         cnt=cnt2=tot=res=0;
    137         cin>>m>>n;
    138         while(char c=getchar()!='\n')c=getchar();
    139         for(sss i=1;i<=n;i++){
    140             cin.getline(g[i]+1,52,'\n');
    141         }
    142         solve();
    143         sort(Edge,Edge+cnt2,cmp);
    144         //for(int i=0;i<=cnt2;i++){
    145         //    cout<<Edge[i].from.x<<" "<<Edge[i].from.y<<" "<<Edge[i].to.x<<" "<<Edge[i].to.y<<" "<<Edge[i].len<<endl;
    146         //}
    147         kersukaer();
    148         cout<<res<<endl;
    149     }
    150     return 0;
    151 }

转载于:https://www.cnblogs.com/greenpepper/p/11327664.html