主题：第52次编程比赛题目
crossbow [专家分：150] 发布于 2007-04-08 19:00:00
(麻烦bm设置sticky)
天还亮着，看着不像晚上，不过就现在放出来吧，不拖了
给出一个简单无向图G=(V,E)，图里面没有偶圈，对于其中指定的两个顶点u和v，计算从u到v的路径的数目。
解答用C或C++应该实现如下接口：
void solve(int n, int m, const int *e, int u, int v);
其中n=|V|即顶点数，m=|E|即边数。所有顶点按0,1,2...,n-1编号。e指向一个有2m个整数的数组，e[2*i]和e[2*i+1]（i=0,1,2,...,m-1）表示一条边的两个端点。u,v就是两个指定的顶点。
允许编写其他函数。允许自行定义数据结构。只允许包含C或C++的标准库的头文件。请明确指定代码使用C还是C++编译。
solve和其他函数只允许向标准输出（stdout）输出数据。输出数据只能包括一行，这一行的内容只能包括用十进制表示的答案。答案前后不能有空格、Tab，不能有多余的前导0。
测试程序只包括一个文件，框架如下：
#include <stdio.h> /* C */
#include <cstdio> /* C++ */
/*
解答内容在此，包括solve函数
*/
int main(void)
{
用scanf之类的东西读入n, m, e, u, v;
solve(n, m, e, u, v);
return 0;
}
提示：
1. （无向图就不解释了，各位翻翻课本吧。）简单图不包含自环和两条首尾相同的边。圈和路径都不包含重复顶点。偶圈就是长度是偶数（当然不能是0啦）的圈。
2. V和E的大小原则上没有特殊限制，以保持测试机器稳定运行和遵从内存限制为限。
3. 测试时，将会允许充分的内存空间，但是原则上栈空间不超过32M，总空间不超过256M。
4. 测试时，时间限制将参考一个Java程序的运行时间（解释语言啊，足够放水的了）。
5. 测试时，作为扩展要求，存在至少一组数据，unsigned __int64/long long存不下结果，做对的将有额外的优势。基本要求下unsigned __int64/long long都没有问题。
6. 测试时用的编译器是MinGW gcc/g++ 3.4.2。出现编译错的代码我原则上不会去修改。
7. 代码要求不能太乱，复杂的逻辑最好加上注释。如果代码因为非技术原因让我看不懂的话，很可能影响最后的评价。
8. 在保证正确性和程序可运行的前提下，请首先尽量降低算法的时间复杂度，其次才考虑运行效率。
9. 放水提示：考虑图的双连通分量。
回复列表 （共18个回复）
沙发
雨中飞燕 [专家分：18980] 发布于 2007-04-08 19:12:00
偶不会，所以偶放弃了，呵呵
板凳
wsygbhjdr [专家分：0] 发布于 2007-04-08 20:15:00
这个编译器的输入输出格式是不是有点什么要求的啊
应该讲清楚的嘛
3 楼
ablised [专家分：0] 发布于 2007-04-09 13:14:00
看看
4 楼
qq282013257 [专家分：0] 发布于 2007-04-10 17:58:00
厉害·！支持
以后多多指点
5 楼
江南孤峰 [专家分：1520] 发布于 2007-04-11 09:47:00
/* 编译环境 VC++ 或者 TC
* LZ说要用标准C，不知道标准C里有没有 unsigned __int64 这种类型
* 如果有，麻烦将solve()函数里的 count 改为该类型，同时输出也做
* 相应的修改。count 我定义为 unsigned long 型,如果路径超过该类
* 型的表示范围就会出错，真要满足任意条路径就只有用数组了。感觉
* 没必要，题目主要是找路径的算法而不是处理怎样表示大数。下面的
* 程序提供了打印路径的函数，只要在 solve() 中打开该函数就可以打
* 印路径了。LZ要求用GCC编译，我没用过，我想应该能够编译通过，因
* 为我用的都是标准的C函数。
*/
#include <stdio.h>
#include <stdlib.h>
/* 链栈，存储路径中边信息 */
typedef struct stack{
int i; /* 图中的节点编号 */
struct stack *next;
}STACK;
/* 以下结构存储一个链栈，我们暂时称它堆栈容器 */
typedef struct node{
STACK *ptop; /* 链栈栈顶 */
struct node *pre;/* 前一个堆栈容器 */
struct node *next;/* 后一个堆栈容器 */
}NODE;
/* 拷贝“常量”边数组 */
void mycpy(int *ed,const int *e,int m){
int i;
for(i = 0; i < m; i += 2){
*(ed+i) = *(e+i);
*(ed+i+1) = *(e+i+1);
}
}
/* 对边数组排序 */
void orderEg(int *ed,int m){
int i,j,temp,n;
for(i = 0; i < m; i += 2)
if(*(ed+i) > *(ed+i+1)){
temp = *(ed+i);
*(ed+i) = *(ed+i+1);
*(ed+i+1) = temp;
}
for(i = 0; i < m; i += 2)
for(j = 0,n = m-i-2; j < n; j += 2)
if(*(ed+j) > *(ed+j+2)){
temp = *(ed+j);
*(ed+j) = *(ed+j+2);
*(ed+j+2) = temp;
temp = *(ed+j+1);
*(ed+j+1) = *(ed+j+3);
*(ed+j+3) = temp;
}
}
/* 新堆栈节点 */
STACK* newStack(void){
STACK *p;
if((p=(STACK*)malloc(sizeof(STACK)))==NULL){
fprintf(stderr,"Alloc memory failed !\n");
exit(1);
}
p->next = NULL;
p->i = 0;
return p;
}
/* 新堆栈容器节点 */
NODE* newNode(void){
NODE *p;
if((p=(NODE*)malloc(sizeof(NODE)))==NULL){
fprintf(stderr,"Alloc memory failed !\n");
exit(1);
}
p->next = NULL;
p->pre = NULL;
p->ptop = NULL;
return p;
}
/* 测试顶点 i 是否有效 */
int test(int i,NODE *pnode){
while(pnode){
if(i == pnode->ptop->i)
return 0;
pnode = pnode->pre;
}
return 1;
}
/* 附加函数：测试时用于打印路径 */
void printPath(NODE *pnode){
while(pnode->pre)
pnode = pnode->pre;
while(pnode->next){
printf("%d-",pnode->ptop->i);
pnode = pnode->next;
}
printf("%d\n",pnode->ptop->i);
}
/* 下接，晕竟然放不下 */
6 楼
江南孤峰 [专家分：1520] 发布于 2007-04-11 09:48:00
/* 初始化堆栈容器 */
NODE* initNode(int *ed,int m,int u){
NODE *pnode,*ptemp;
STACK *pstack;
int i,j;
pstack = newStack();
pstack->i = u;
pnode = newNode();
pnode->ptop = pstack;
ptemp = newNode();
for(i = 0; i < m; i += 2){
if(*(ed+i) > u)
break;
if(*(ed+i) == u)
j = *(ed+i+1);
else if(*(ed+i+1) == u)
j = *(ed+i);
else
continue;
pstack = newStack();
pstack->i = j;
pstack->next = ptemp->ptop;
ptemp->ptop = pstack;
}
if(!ptemp->ptop){
free(ptemp);
free(pnode->ptop);
free(pnode);
return NULL;
}
pnode->next = ptemp;
ptemp->pre = pnode;
return ptemp;
}
/* 这个函数就是核心了 */
void solve(int n, int m, const int *e, int u, int v){
unsigned long count = 0;/* 标准C里没有unsigned __int64 吧!*/
int *ed = (int*)malloc(sizeof(int)*m);
int i;
NODE *pnode,*ptemp;
STACK *pstack;
mycpy(ed,e,m);
orderEg(ed,m);
if(!(pnode=initNode(ed,m,u))){
printf("0\n");
return ;
}
while(1){
if(!pnode->ptop){ /* 一个堆栈为空 */
ptemp = pnode;/* 堆栈容器节点将被释放 */
pnode = pnode->pre;
pnode->next = NULL;
free(ptemp);
if(pnode->ptop->i==u)
break;
pstack = pnode->ptop;
pnode->ptop = pnode->ptop->next;
free(pstack);
continue;
}
if(pnode->ptop->i == v){/* 找到路径 */
/* printPath(pnode); 测试调用该函数打印路径 */
count ++;
pstack = pnode->ptop;
pnode->ptop = pstack->next;
free(pstack);
continue;
}
ptemp = newNode();
for(i = 0; i < m; i += 2){
if(*(ed+i) > pnode->ptop->i)
break;
if( (*(ed+i)!=pnode->ptop->i && *(ed+i+1)!=pnode->ptop->i)||
(*(ed+i)==pnode->ptop->i && !test(*(ed+i+1),pnode))||
(*(ed+i+1)==pnode->ptop->i && !test(*(ed+i),pnode)) )
continue;
pstack = newStack(); /* 准备进栈 */
if(*(ed+i) == pnode->ptop->i)
pstack->i = *(ed+i+1);
else
pstack->i = *(ed+i);
pstack->next = ptemp->ptop;
ptemp->ptop = pstack;
}
if(!ptemp->ptop){/* 该路径无法延续下去 */
free(ptemp);
pstack = pnode->ptop;
pnode->ptop = pstack->next;
free(pstack);
continue;
}
else{/* 正常延续路径 */
pnode->next = ptemp;
ptemp->pre = pnode;
pnode = ptemp;
}
}
printf("%ld\n",count);
free(pnode->ptop);
free(pnode);
}
int main(){
int n,m,u,v;
int *e,i;
scanf("%d%d",&n,&m);
m *= 2;
e = (int*)malloc(sizeof(int)*m);
for(i = 0; i < m; i+=2)
scanf("%d%d",e+i,e+i+1);
scanf("%d%d",&u,&v);
solve(n,m,e,u,v);
free(e);
return 0;
}
7 楼
yinnanjing [专家分：0] 发布于 2007-04-11 15:41:00
内容隐藏，本帖结帖后才能浏览。
8 楼
csea [专家分：340] 发布于 2007-04-12 00:38:00
双向广搜，不知道行不行
学习中。。。。
9 楼
worton [专家分：0] 发布于 2007-04-12 11:30:00
/*C语言编写*/
/*深度优先搜索*/
# include <stdio.h>
# include <stdlib.h> /*for malloc()*/
int* visited; /*辅助数组，标记点是否已访问*/
int** list; /*用二维数组模拟邻接表，并非邻接矩阵*/
int result[100]={0}; /*存储十进制结果，低位存储在头部，最多100位，好像有点太大啊*/
int pointer; /*指向结果的最高位，初值为0*/
void solve(int n, int m, const int *e, int u, int v); /*声明一下, u !=v */
void DFS_solve (int n, int m, int u, int v);
void add (void); /*递增结果*/
int main()
{
int i, n, m, u, v, *e;
/*
freopen ("in.txt", "r", stdin);
freopen ("out.txt", "w", stdout);
*/
/*读取数据并分配空间*/
scanf ("%d%d", &n, &m); /*读取n，m*/
e = (int*)malloc (2*m*sizeof(int)); /*为e分配2m个空间*/
for (i = 0; i < m; i++) /*读取m条边*/
scanf ("%d%d", &e[2*i], &e[2*i+1]);
scanf ("%d%d", &u, &v);
solve (n, m, e, u, v);
/*输出结果*/
for (i = pointer; i >= 0; i--)
printf ("%d", result[i]);
putchar ('\n');
return 0;
}
void solve(int n, int m, const int *e, int u, int v)
{
int i, k;
list = (int**)malloc (n*sizeof(int*));
visited = (int*)malloc (n*sizeof(int));
for (i = 0; i < n; i++)
{
visited[i] = 0;
list[i] = (int*)malloc (n*sizeof(int));/*本来最多n-1个邻接点，多出第一个位置存储邻接点个数*/
list[i][0] = 0; /*初始化每个点的邻接点个数为0 */
}
/*建立邻接表*/
for (i = 0; i < m; i++)
{
k = ++list[e[2*i]][0];/*点e[2*i]的邻接点个数加1*/
list[e[2*i]][k] = e[2*i+1];
k = ++list[e[2*i+1]][0];/*点e[2*i+1]的邻接点个数加1*/
list[e[2*i+1]][k] = e[2*i];
}
DFS_solve (n, m, u, v);
}
void DFS_solve (int n, int m, int u, int v)
{
int i;
visited[u] = 1; /*标记访问*/
if (u == v) /*找到一个结果*/
add();
if (list[u][0] != 0)
{
for (i = 1; i <= list[u][0]; i++)
{
if (!visited[list[u][i]] /*|| list[u][i]==v*/)
DFS_solve (n, m, list[u][i], v);
}
}
visited[u] = 0; /*恢复，回溯之用*/
}
void add (void)
{
int j = 0;
while (result[j]+1 == 10)
{
result[j] = 0;
j++;
}
result[j]++;
if (j > pointer)
pointer = j;
}
10 楼
zeyu1987 [专家分：0] 发布于 2007-04-12 23:02:00
看看..........
我来回复
您所在位置：