好久没写，最近都做了很多基础题，什么各种最短路，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 阅读(1313)
评论(0) 编辑 收藏 引用