学校选址.cpp

学校选址问题

#define Max   999 
#include<stdio.h>
#include<stdlib.h>
#include<iomanip.h>
struct graph  {
       char  vexlist[200];
       int   edge[200][200];
       int  n,e;
        }MTgraph;
void CreatGraphic()
     {
            int i,j,k,w;
           
             printf("请输入图的顶点数和边数:\n");
            
             scanf("%d,%d",&MTgraph.n,&MTgraph.e);
            
             for(i=1;i<=MTgraph.n;i++)
                   
                   for(j=1;j<=MTgraph.n;j++)
                       
                       MTgraph.edge[i][j]=Max;
            for(i=1;i<=MTgraph.n;i++)
                   
                   MTgraph.edge[i][i]=0;
                   
                   printf("请您在图中的节点输入(i,j,w)表示从i到j的权值为w\n");
                   
                   printf("如：1,2,3 回车表示第一个节点到第二个节点的权值为3\n");
            for(k=1;k<=MTgraph.e;k++)
                        {
                            scanf("%d,%d,%d",&i,&j,&w);
                            MTgraph.edge[i][j]=w;
                            //MTgraph.edge[j][i]=w;
                            }
                printf("输入的邻接矩阵为：\n");   
         
                 for(i=1;i<=MTgraph.n;i++)//输出建立的邻接矩阵// 
                     {
                          for(j=1;j<=MTgraph.n;j++)
                          {
                           if(MTgraph.edge[i][j]==Max)
                               
                               printf("∞ "); 
                           else
                               
                               printf("%2d",MTgraph.edge[i][j]);
                               }
                     printf("\n"); 
                    }
                    
      } 
      void floyd()
     {
      int a[100][100],p[100][100],c[100];
      int k,i,j,temp;
      char ch; 
      for(i=0;i<MTgraph.n;i++)
           {
             for(j=0;j<MTgraph.n;j++)
               {
                a[i][j]=MTgraph.edge[i][j];
                p[i][j]=0;
               }
            }
       for(k=0;k<MTgraph.n;k++)
           for(i=0;i<<MTgraph.n;i++)
               for(j=0;j<MTgraph.n;j++)
                    if(a[i][k]+a[k][j]<a[i][j])
                         {
                           a[i][j]=a[i][k]+a[k][j];
                           p[i][j]=k;
                          }
        for(j=0;j<MTgraph.n;j++)
            {
              temp=a[0][j];
              for(i=0;i<MTgraph.n;i++)
                 {
                  if(a[i][j]>temp)
                     temp=a[i][j];
                  }
               printf("结点：%d  ",MTgraph.vexlist[j]);
               if(temp==10000)
                  printf("偏心度：∞\n");
               else printf("偏心度：%d\n",temp);
               c[j]=temp;
             }
        temp=c[0];
        for(i=1;i<MTgraph.n;i++)
              if(temp>c[i])
                 {
                  temp=c[i];
                  k=i;
                  }
         printf("中心点： %d",MTgraph.vexlist[k]);
         ch=getchar();
         ch=getchar(); 
      }

     int main()

{ char ch;
   
  
   do 
                {

                     //system("cls");

                     printf("*******学校选址程序 written by QiaoMu CST HIT*******\n");



                     printf("%s","(S)tart开始输入图节点数据\n");

                     printf("%s","(E)xit退出\n");

                     printf("%s","请输入选择:");

                     scanf("%c",&ch);

                     ch=toupper(ch);//保证大小写均可 

            }while(ch!='S'&&ch!='E');

          switch(ch)

          {

           case'S':
          CreatGraphic(); 
           floyd(); 
            break;
            case'E': 
            return 1;

          }
          int q; scanf("%d",&q);
     
}