摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:最小生成樹
應用:DFS+BFS(一點都不誇張)
想法:因為最小生成樹的演算法,我一點也不了解,老師別罵我嘿,所以我採用DFS舉出所有可能的邊,BFS看看是否為一棵樹

小心:輸出的部份要照給的順序輸出,而且還要排序=ˇ=

/***********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*枚舉所有可能 再利用BFS搜索是否為全部相連*/
int map[11][11]={0};
int n,m,data;
int minmap[11][11]={0},min=2147483647,way[11][11]={0},appear[11]={0};
void make (int now) /*NOW為點*/
{
  int a,b,c;
  if(now==n+1)/*BFS*/
   {
    int flag[11]={0},queue[12]={0},top=0;
    for(a=1;a<=n;a++)
     if(appear[a]!=0) break;
    queue[0]=a;/*從起點1走*/
    for(a=0;a<=top;a++)
     for(b=1;b<=n;b++)
       if(way[queue[a]][b]==1&&flag[b]==0)/*0為尚未走過*/
        {
          top++;
          flag[b]=1;
          queue[top]=b;
        }
     for(a=1;a<=n;a++)
      if(flag[a]!=appear[a]) break;
      if(a==n+1)/*成為全部相連圖*/
       {
       int sum=0;
        for(b=1;b<=n;b++)
         for(c=1;c<=b;c++)
          if(way[b][c]==1) sum=sum+map[b][c];
         if(sum<min)
          {
            min=sum;
            for(b=1;b<=n;b++)
             for(c=1;c<=n;c++)
              minmap[b][c]=way[b][c];
          }
       }
   }
  else
  {
  if(appear[now]==1)
  for(a=1;a<=n;a++)
      if(map[now][a]!=0)
       {
         way[now][a]=1;
         way[a][now]=1;
         make(now+1);
         way[now][a]=0;
         way[a][now]=0;
       } 
   }   
   if(appear[now]==0&&now+1<=n) make(now+1);
}
main()
{
 
 char x[10],y[10],time=0;
 while(scanf("%d %d",&n,&m)==2)
  {
    time++;
   
    int a,b,c;
    for(a=0;a<11;a++)
     for(b=0;b<11;b++)
      {
        way[a][b]=0;
        map[a][b]=0;
        minmap[a][b]=0;
        appear[a]=0;
      }
     int output[11][2]={0},top=0,input[100][2]={0};
     for(a=0;a<m;a++)
      {
        int tempx,tempy;
        scanf("%s %s %d",x,y,&data);
        if(strlen(x)==2) tempx=x[1]-48;
        if(strlen(x)==3) tempx=(x[1]-48)*10+x[2]-48;
        if(strlen(y)==2) tempy=y[1]-48;
        if(strlen(y)==3) tempy=(y[1]-48)*10+y[2]-48;
        map[tempx][tempy]=data;
        map[tempy][tempx]=data;
        input[a][0]=tempx;input[a][1]=tempy;
        appear[tempx]=1;appear[tempy]=1;      
      }
    min=2147483647;
    make(1);
    for(b=1;b<=n;b++)
      for(c=b;c<=n;c++)
          if(minmap[b][c]==1) {
                               for(a=0;a<m;a++)
                                if(input[a][0]==b&&input[a][1]==c) break;
                               if(a!=m)
                               {output[top][0]=b;output[top][1]=c;}
                               else
                               {output[top][0]=c;output[top][1]=b;}
                               top++;
                              }
   for(a=0;a<top;a++)
    {
     c=a;
      for(b=a+1;b<top;b++)
       if(output[b][0]<output[c][0]||(output[b][0]==output[c][0]&&output[b][1]<output[c][1])) c=b;
      int temp,temp1;
      temp=output[c][0];
      temp1=output[c][1];
      output[c][0]=output[a][0];
      output[c][1]=output[a][1];
      output[a][0]=temp;
      output[a][1]=temp1; 
      printf("(W%d W%d) ",output[a][0],output[a][1]);
    }
    
   printf("\n%d\n",min);
  }
 return 0;
}
/*
7  11
W1 W2 1
W1 W4 4
W2 W3 2
W2 W4 6
W2 W5 4
W3 W5 5
W3 W6 6
W4 W5 3
W4 W7 4
W5 W6 8
W6 W7 3
10 7
W10 W2 5
W10 W3 10
W10 W6 8
W2 W3 4
W3 W4 2
W3 W5 1
W3 W6 7
*/