csp20170304地铁修建_Solution-白红宇

csp20170304地铁修建_Solution

阅读量：4349 次

发布时间：2019-06-07

本文共 7731 字，大约阅读时间需要 25 分钟。

ccf20170304地铁修建_Solution

这里最短路为所以从点1到点n的路径中最长的道路的长度。

因为1 ≤ n ≤ 100000，1 ≤ m ≤ 200000，属于稀疏图，所以使用Spfa(循环队列)较适合，如果使用dijkstra需要堆优化。

其实这道题用并查集最好，对所有道路长度从小到大排序，依次添加道路，直到点1和点n相连(属于同一个集合)。

1.并查集

1 #include 
     
       2 #include 
      
        3 #define maxn 100000 4 #define maxm 200000 5  6 //并查集 UnionFind 7 //171s 8  9 struct node10 {11     long x,y,len;12 };13 14 long father[maxn+1];15 16 long cmp(const void *a,const void *b)17 {18     return (*(struct node *)a).len-(*(struct node *)b).len;19 }20 21 long getfather(long d)22 {23     if (father[d]==d)24         return d;25     father[d]=getfather(father[d]);26     return father[d];27 }28 29 int main()30 {31     long n,m,i,u,v;32     struct node *road=(struct node *) malloc (sizeof(struct node)*(maxm+1));33     scanf("%ld%ld",&n,&m);34     for (i=1;i<=m;i++)35         scanf("%ld%ld%ld",&road[i].x,&road[i].y,&road[i].len);36     qsort(&road[1],m,sizeof(struct node),cmp);37     for (i=1;i<=n;i++)38         father[i]=i;39     //边从小到大 加入图中，直到1到n可达40     //每次加边(x,y) father[y]=x41     for (i=1;i<=m;i++)42     {43         u=getfather(road[i].x);44         v=getfather(road[i].y);45         father[v]=u;46 47         //每一次判断1,n的父亲是否相同，如果是，即1到n可达48         if (getfather(father[1])==getfather(father[n]))49             break;50     }51     //即1到n必经过该边i，而该边长度最长52     printf("%ld\n",road[i].len);53     return 0;54 }

2.Spfa(循环队列)

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #define maxn 100000  6 #define maxm 200000  7 #define maxc 1000000  8   9 long max(long a,long b) 10 { 11     if (a>b) 12         return a; 13     else 14         return b; 15 } 16  17 int main() 18 { 19     struct node 20     { 21         long d,len; 22         struct node *next; 23     }; 24     long n,m,head,tail,d,value,i,a,b,c; 25     long *dis=(long *) malloc (sizeof(long)*(maxn+1)); 26     //循环队列 27     long *line=(long *) malloc (sizeof(long)*(maxn+1)); 28     bool *vis=(bool *) malloc (sizeof(bool)*(maxn+1)); 29     //本身已经是struct node *point，创建数组再加"*" 30     struct node **point=(struct node **) malloc (sizeof(struct node *)*(maxn+1)); 31     struct node *t; 32     scanf("%ld%ld",&n,&m); 33  34     for (i=1;i<=n;i++) 35     { 36         point[i]=NULL; 37         //1 ≤ c ≤ 1000000 38         //max<=c 39         dis[i]=maxc; 40         vis[i]=true; 41     } 42     for (i=1;i<=m;i++) 43     { 44         scanf("%ld%ld%ld",&a,&b,&c); 45         //build a 46         t=(struct node *) malloc (sizeof(struct node)); 47         t->d=b; 48         t->len=c; 49         if (point[a]!=NULL) 50             t->next=point[a]; 51         else 52             t->next=NULL; 53         point[a]=t; 54         //build b 55         t=(struct node *) malloc (sizeof(struct node)); 56         t->d=a; 57         t->len=c; 58         if (point[b]!=NULL) 59             t->next=point[b]; 60         else 61             t->next=NULL; 62         point[b]=t; 63     } 64     dis[1]=0; 65     vis[1]=false; 66     line[1]=1; 67     //head=front-1 牺牲一个位置 front为队列头位置 68     head=0; 69     tail=1; 70     //这里的循环队列不用判断空或者溢出 71     //因为如果那样的话，已经不能用了。 72     //不存在空的情况。而数组要开的足够大，使队列不溢出。 73     while (head!=tail) 74     { 75         //head++; 76         //队列为0~n 77         head++; 78         if (head==n+1) 79             head=0; 80         d=line[head]; 81         t=point[d]; 82         while (t) 83         { 84             if (dis[d]
         
          len) 85                 value=t->len; 86             else 87                 value=dis[d]; 88             if (value
          
           d]) 89 { 90 dis[t->d]=value; 91 //如果该点未被放在队列里，则入队；否则不入队 92 //即在队列里的点都不重复 93 //则队列(tail-head)最多有n+1个数(n个点+空位置(head)) 94 if (vis[t->d]) 95 { 96 //tail++; 97 tail++; 98 if (tail==n+1) 99 tail=0;100 line[tail]=t->d;101 vis[t->d]=false;102 }103 }104 t=t->next;105 }106 vis[d]=true;107 }108 printf("%ld\n",dis[n]);109 return 0;110 }

3.dijkstra(80 Points)

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define maxn 100000 6 #define maxm 200000 7 #define maxc 1000000 8 #define maxdist 1000000000 9 10 //裸dijkstra 80分 超时11 12 long max(long a,long b)13 {14     if (a>b)15         return a;16     else17         return b;18 }19 20 int main()21 {22     struct node23     {24         long d,len;25         struct node *next;26     };27     struct node **point=(struct node **) malloc (sizeof(struct node *)*(maxn+1));28     struct node *p;29     bool *vis=(bool *) malloc (sizeof(bool)*(maxn+1));30     long *dist=(long *) malloc (sizeof(long)*(maxn+1));31     long n,m,i,j,a,b,c,d,value,mindist;32     scanf("%ld%ld",&n,&m);33     for (i=1;i<=n;i++)34     {35         point[i]=NULL;36         dist[i]=maxc;37         vis[i]=true;38     }39     for (i=1;i<=m;i++)40     {41         scanf("%ld%ld%ld",&a,&b,&c);42         //build a43         p=(struct node *) malloc (sizeof(struct node));44         p->d=b;45         p->len=c;46         if (point[a]!=NULL)47             p->next=point[a];48         else49             p->next=NULL;50         point[a]=p;51         //build b52         p=(struct node *) malloc (sizeof(struct node));53         p->d=a;54         p->len=c;55         if (point[b]!=NULL)56             p->next=point[b];57         else58             p->next=NULL;59         point[b]=p;60     }61     for (i=1;i<=n;i++)62     {63         vis[i]=true;64         dist[i]=maxdist;65     }66     //从点1开始67     dist[1]=0;68     d=1;69     vis[1]=false;70     for (i=1;i
         
          len)76                 value=p->len;77             else78                 value=dist[d];79             if (value
          
           d])80 dist[p->d]=value;81 p=p->next;82 }83 mindist=maxdist;84 for (j=2;j<=n;j++)85 if (vis[j] && dist[j]

4.dijkstra堆优化

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define maxn 100000 6 #define maxm 200000 7 #define maxc 1000000 8 #define maxdist 1000000000 9 10 //裸dijkstra 80分 超时11 12 long max(long a,long b)13 {14     if (a>b)15         return a;16     else17         return b;18 }19 20 int main()21 {22     struct node23     {24         long d,len;25         struct node *next;26     };27     struct node **point=(struct node **) malloc (sizeof(struct node *)*(maxn+1));28     struct node *p;29     bool *vis=(bool *) malloc (sizeof(bool)*(maxn+1));30     long *dist=(long *) malloc (sizeof(long)*(maxn+1));31     long n,m,i,j,a,b,c,d,value,mindist;32     scanf("%ld%ld",&n,&m);33     for (i=1;i<=n;i++)34     {35         point[i]=NULL;36         dist[i]=maxc;37         vis[i]=true;38     }39     for (i=1;i<=m;i++)40     {41         scanf("%ld%ld%ld",&a,&b,&c);42         //build a43         p=(struct node *) malloc (sizeof(struct node));44         p->d=b;45         p->len=c;46         if (point[a]!=NULL)47             p->next=point[a];48         else49             p->next=NULL;50         point[a]=p;51         //build b52         p=(struct node *) malloc (sizeof(struct node));53         p->d=a;54         p->len=c;55         if (point[b]!=NULL)56             p->next=point[b];57         else58             p->next=NULL;59         point[b]=p;60     }61     for (i=1;i<=n;i++)62     {63         vis[i]=true;64         dist[i]=maxdist;65     }66     //从点1开始67     dist[1]=0;68     d=1;69     vis[1]=false;70     for (i=1;i
         
          len)76                 value=p->len;77             else78                 value=dist[d];79             if (value
          
           d])80 dist[p->d]=value;81 p=p->next;82 }83 mindist=maxdist;84 for (j=2;j<=n;j++)85 if (vis[j] && dist[j]