The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

南航4.18省赛A题 解题报告

原题:

                                                                                                   城市规划

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:75            测试通过:13

描述

NanJing准备开发一片荒地,目前已经规划好了一些居民点,还要建设道路。由于经费问题,现在想在保持任意两点间的距离最短的前提下,用尽可能少的经费把这些点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。现在给出两两居民点间的花费,当然了,花费和路径长度成正比~

 

输入

第一行是个N<=100,表示N个居民点。

下面是个N*N的矩阵,第i行第j列,表示ij的花费,可能有负数,表示两地不相连。保证有解。

 

输出

输出一行为总花费。

 

样例输入

3
0 2 1
2 0 3
1 3 0

样例输出

3

提示

这里建设12 13这两条路。




刚拿到这道题还以为是floyd,仔细看看才发现发现原来不是。
题目中说要保证每个顶点之间的距离最短,也就是说在某个源点到其他点的最短路径上的通路必须保留,其余的边可以滤去;
我的第一个想法是不断的调用DIJ把每个点到其他点的最短路求出来,不过这样有的边会被重复加。
后来又有了第二个想法,就是用一个二维矩阵做为标志,如果这条边(u,v)已经被访问过,那么map[u][v]置成1,这样便解决了重复添加的问题。
这样应该对了吧?我当时也是这样认为的,可惜结果不然。
如果两点间有两条最短路同时存在的情况,该怎么办呢?由于DIJ每一次循环都会找到一条最短路径,那么当用这个确定点去更新其他点的信息时,要使用dis[mark]+map[mark][i]<=di[i]而不是<,这样当出现两条或者两条以上的最短路路时会优先选择已经选择过的点,这样便解决了优先权的问题。
好了,经历的这三个步骤,代码终于AC.呵呵 (Wa了四次)

#include<iostream>
#include
<algorithm>
using namespace std;
#define MAX 101
#define MAX_INT 999999999


int mymap[MAX][MAX];
int visit[MAX];
int dis[MAX];
int pre[MAX];
int record[MAX][MAX];
int n;




int  Dij_plus(int s)
{
    
int result=0;
    memset(visit,
0,sizeof(visit));
    memset(pre,
0,sizeof(pre));
    
int i,j;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=mymap[s][i];
    }

    visit[s]
=1;
    
int temp=MAX_INT;
    
int mark;
    
for(i=1;i<=n;i++)
        pre[i]
=-1;
    
for(i=1;i<=n;i++)
    
{
        
        
if(visit[i]!=1&&mymap[s][i]!=MAX_INT)
            pre[i]
=s;
    }

    
    
for(j=1;j<=n-1;j++)
    
{
        temp
=MAX_INT;
        
for(i=1;i<=n;i++)
        
{
            
            
if(visit[i]!=1&&dis[i]<temp)
            
{
                temp
=dis[i];
                mark
=i;
            }

        }

        visit[mark]
=1;
        
if(record[pre[mark]][mark]==0)
        
{
            record[pre[mark]][mark]
=1;
            record[mark][pre[mark]]
=1;
            result
+=mymap[pre[mark]][mark];
        }


        
for(i=1;i<=n;i++)
        
{
            
            
if(visit[i]!=1&&mymap[mark][i]+dis[mark]<=dis[i])
            
{
                dis[i]
=mymap[mark][i]+dis[mark];
                pre[i]
=mark;
            }

            
        }

    }

    
return result;
}


int main ()
{

    
int i,j;
    
int result=0;
    scanf(
"%d",&n);
    
for(i=1;i<=n;i++)
    
{
        
for(j=1;j<=n;j++)
        
{

            
int temp;
            scanf(
"%d",&temp);
            
if(temp<0)
            
{
                mymap[i][j]
=MAX_INT;
                mymap[j][i]
=MAX_INT;
                
continue;
            }

            mymap[i][j]
=temp;
            mymap[j][i]
=temp;

        }

    }

    
for(i=1;i<=n;i++)
    
{

        result
+=Dij_plus(i);
    }

    printf(
"%d\n",result);
    system(
"pause");
    
return 0;
}
 



posted on 2009-04-19 19:15 abilitytao 阅读(1219) 评论(2)  编辑 收藏 引用

评论

# re: 南航4.18省赛A题 解题报告 2009-04-22 22:51 zhongxiaobin

很像运筹学书上的一道题目。  回复  更多评论   

# re: 南航4.18省赛A题 解题报告 2009-04-23 00:39 abilitytao

@zhongxiaobin
是吗?能不能具体说说属于运筹学的哪个问题呢 我想去看看关于这个问题的书  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理