posts - 10,  comments - 14,  trackbacks - 0
好久没写,最近都做了很多基础题,什么各种最短路,BFS,DFS,最小生成树啊,等等等等。
然后今天下午在看网络流,看累了跑去南航OJ看看,这里果然动不动就有比赛的。于是开始A题。
一开始很顺利1次通过A了3道,接着就试着做剩下的题,发现都不是很好解决。后来就盯着道最短路的做,题目意思就是求一图给定两点间的所有最短路所包含的点的个数,关键是所有最短路,而不是只有一条。由于对于一个图会问很多对点的值,再加上两点之间,很容易就先想到FLOYD,但是怎样求出所有最短路呢?我是用的FLOYD求出路长之后,用带有深度限制的深搜求得的,就是深度超过了两点间的最短路大小(前面FLOYD已求出)就停止,并且要回朔点的记忆,就是再深搜完这个分支回朔时要置回这个点的VISIT为0。题目链接为http://acm.nuaa.edu.cn/problemdetail.do?&method=showdetail&id=1579
代码是:
#include<iostream>
using namespace std;
#define INF 10000000
int mat[110][110];
int sh[110][110];
int re[110],visit[110],pre[110];
void dfs(int x,int y,int n,int step,int limit)
{
    
if(step>=limit)
        
return;
   
for(int i=1;i<=n;i++)
        
if(!visit[i]&&mat[x][i]>0)
        
{
            
if(i==y)
            
{
                
int cur=x;
                
while(pre[cur])
                
{
                    re[cur]
=1;
                    cur
=pre[cur];
                }

            }

            
else
            
{
                pre[i]
=x;
                visit[i]
=1;
                dfs(i,y,n,step
+1,limit);
                visit[i]
=0;
            }

        }

}

int DFS(int x, int y, int n)
{
    memset(visit,
0,sizeof(visit));
    memset(pre,
0,sizeof(pre));
    memset(re,
0,sizeof(re));
    
int num=0;
    visit[x]
=1;
    dfs(x,y,n,
0,sh[x][y]); 
    
for(int i=1;i<=n;i++)
        
if(re[i])
            num
++;
    
return num+2;
}


int main()
{
    
int n,m,x,y,p;
    scanf(
"%d%d",&n,&m);
    
while(m--)
    
{
        scanf(
"%d%d",&x,&y);
        mat[x][y]
=1;
        mat[y][x]
=1;
    }

    
for(int i=1;i<=n;i++)
        
for(int j=1;j<=n;j++)
        
{
            
if(mat[i][j])
                sh[i][j]
=mat[i][j];
            
else
                sh[i][j]
=INF;
        }

    
for(int k=1;k<=n;k++)
        
for(int i=1;i<=n;i++)
            
for(int j=1;j<=n;j++)
                
if(sh[i][k]+sh[k][j]<sh[i][j])
                    sh[i][j]
=sh[i][k]+sh[k][j];
    scanf(
"%d",&p);
    
while(p--)
    
{
        scanf(
"%d%d",&x,&y);
        printf(
"%d\n",DFS(x,y,n));
    }

    
return 0;
}
 


接着再做了一道题,提交时发现比赛正好结束了2分钟,于是去吃饭咯。这题用了个小技巧解决了超时问题,题目意思很简单就是按顺序给了一连串的数,要在每个数之前给的数中找到一个和自己最接近的数,求与它差的绝对值,求把每个数的这个值相加得到的值。题目链接为:
http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1123
一开始想到就是按值排序,然后左右搜第一个序号比自己小的,再选差值小的求绝对值。后来想到先排序,再把排序后的序号与原先输入序号对应起来,即可以通过原先输入的顺序遍历(即按序号大小顺序遍历),在遍历过程中能常数时间访问到它在按值排序数组中的数。这有什么好处呢?就是我只要按序号从大到小遍历,每次找到值排序数组中的数,看它在值排序数组中相邻的两个值,这两个值取最接近的求绝对值即可,求后把当前数从值排序数组中删掉,这样就保证遍历时的当前数在值排序数组中始终是序号最大的,那满足条件的最接近的值就在值排序数组中相邻的两个值中。这样时间复杂度就是排序复杂度,后来的遍历只要0(n)时间。因为我偷懒用的是顺序数组存的,那怎样在数组中把数删掉呢,再找个辅助数组,像链表一样把每个序号的前项和后项记下来就行,这样操作这个辅助数组,就可以达到取相邻值,删除值的效果。具体代码如下:

#include<iostream>
using namespace std;
#include
<cmath>
#include
<algorithm>
#define INF 100000000
struct elem{
    
int i;
    
int v;
    elem(
int i=0,int v=0):i(i),v(v){}
}
;
struct link{
    
int pre;
    
int next;
}
 l[40000];
elem mat[
40000];
elem help[
40000];

bool com(elem x, elem y)
{
    
return x.v<y.v;
}

int main()
{
    
int n,x,num=0;
    scanf(
"%d",&n);
    
for(int i=0;i<n;i++)
    
{
        scanf(
"%d",&x);
        mat[i]
=elem(i,x);
        help[i]
=mat[i];
    }

    sort(mat,mat
+n,com);
    
for(int i=0;i<n;i++)
    
{
        help[mat[i].i].i
=i;
        l[i].pre
=i-1;
        l[i].next
=i+1;
    }

    
for(int i=n-1;i>0;i--)
    
{
        
int x=INF,y=INF,pe,ne;
        pe
=l[help[i].i].pre;
        ne
=l[help[i].i].next;
        
if(pe>=0)
        
{
            x
=abs(mat[pe].v-help[i].v);
            l[pe].next
=ne;
        }

        
if(ne<n)
        
{
            y
=abs(mat[ne].v-help[i].v);
            l[ne].pre
=pe;
        }

        num
+=x>y?y:x;
    }

    num
+=help[0].v;
    printf(
"%d\n",num);
    
return 0;
}
 
posted on 2009-07-29 21:38 tortoisewu 阅读(1312) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

留言簿(1)

随笔档案

文章分类

搜索

  •  

最新评论

阅读排行榜

评论排行榜