主题：第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个回复）
11 楼
yccy4004 [专家分：0] 发布于 2007-04-13 11:36:00
哎呀，我看不懂呀。
12 楼
yogafrank [专家分：440] 发布于 2007-04-13 23:53:00
#include <stdio.h>
int count = 0;/*for the solutions*/
/*print the solutions*/
void printpath(int *p, int lenth)
{
int i = 0;
for(i = 0; i < lenth; i++)
printf("%d->", p[i]);
printf("%d", p[i]);
printf("\n");
}
/*use the recursive way to resolve under the condition of u != v*/
void pathall(int n, int u, int v, int **matrix, int *temp, int *path, int lenth, int *visited)
{
int node, i = 1;
int j;
visited[u] = 1;/*indicate that u has been visited*/
lenth++;/*the lenth of path*/
path[lenth] = u;
if(u == v)/*find the path then print it*/
{
count++;
printpath(path, lenth);
}
for(i = 1; i < temp[u]; i++)
{
node = matrix[u][i];
if(visited[node] == 0)
pathall(n, node, v, matrix, temp, path, lenth, visited);
}
visited[u] = 0;/*make u available for the next round*/
lenth--;
}
void solve(int n, int m, const int *e, int u, int v)
{
int i, j, *p;
int **matrix;
int *temp, *path, *visited;
int lenth = -1;
visited = (int*)malloc(sizeof(int) * n);
path = (int*)malloc(sizeof(int) * n);
temp = (int*)malloc(sizeof(int) * n);
for(i = 0; i < n; i++)
{
temp[i] = 1;
path[i] = -1;
visited[i] = 0;
}
/*apply enough memory to create the data structure for the list*/
matrix = (int**)malloc(sizeof(int*) * n);
for(i = 0; i < n; i++)
{
p = (int*)malloc(sizeof(int) * n);
matrix[i] = p;
}
/*initialize the array list*/
/*imitate the 2 dimensional array*/
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
matrix[i][j] = 0;
for(i = 0, j = 0; i < n; i++)
matrix[i][j] = i;
/*create the list*/
for(i = 0; i < 2 * m - 1; i += 2)
{
matrix[e[i]][temp[e[i]]] = e[i + 1];
temp[e[i]]++;
matrix[e[i + 1]][temp[e[i + 1]]] = e[i];
temp[e[i + 1]]++;
}
/*solution for under the condition u == v*/
pathall(n, u, v, matrix, temp, path, lenth, visited);
/*in case of memory leaks*/
for(i = 0; i < n; i++)
free(matrix[i]);
free(matrix);
free(temp);
free(path);
}
int main(void)
{
int i;
int n, m, *e, u, v;
/* freopen("in.txt", "r", stdin); *//*for convenience which is no use*/
scanf("%d%d", &n, &m);
e = (int*)malloc(sizeof(int) * m * 2);
for(i = 0; i <= 2 * m -1; i+=2)
scanf("%d%d", &e[i], &e[i + 1]);
scanf("%d%d", &u, &v);
solve(n, m, e, u, v);/*function required*/
printf("%d\n",count);
free(e);
return 0;
}
13 楼
yxs0001 [专家分：9560] 发布于 2007-04-14 15:25:00
struct VNode{
int mNo;
VNode* mNext;
VNode* mPrior;
};
class CVertex{
private:
int mNo; //顶点编号
int mDegree; //顶点度
VNode* mHead; //链表头
VNode* mTail; //链表尾
VNode* mCur; //当前访问的邻接点
public:
CVertex(){
mDegree = 0;
mHead = new VNode;
mTail = new VNode;
mHead->mNext = mTail;
mHead->mPrior = NULL;
mTail->mNext = NULL;
mTail->mPrior = mHead;
SetCurHead();
}
~CVertex(){
while(mHead->mNext != mTail){
mHead = mHead->mNext;
delete mHead->mPrior;
}
delete mTail;
}
int GetDegree(){
return mDegree;
}
void AddDegree(int No){
VNode* vn = new VNode;
vn->mNo = No;
vn->mPrior = mTail->mPrior;
mTail->mPrior->mNext = vn;
mTail->mPrior = vn;
vn->mNext = mTail;
mDegree ++;
}
void DelDegree(int No){
VNode *vn = mHead->mNext;
while(vn->mNo != No)
vn = vn->mNext;
vn->mPrior->mNext = vn->mNext;
vn->mNext->mPrior = vn->mPrior;
delete vn;
mDegree --;
}
VNode* GetCurNode(){
return mCur;
}
void SetCurHead(){
mCur = mHead;
}
bool SetCurNext(){
if(mCur->mNext == mTail)
return false;
else
mCur = mCur->mNext;
return true;
}
void SetNo(int No){
mNo = No;
}
void Show(){
cout<<" 顶点编号："<<mNo<<" 度："<<mDegree<<" 相邻顶点：";
VNode* vn = mHead;
while(vn->mNext != mTail){
vn = vn->mNext;
cout<<vn->mNo<<" ";
}
cout<<endl;
}
};
14 楼
yxs0001 [专家分：9560] 发布于 2007-04-14 15:25:00
续上
class CGraph{
private:
CVertex* mCV;
int mn;
int mu,mv;
void MySet(int n,int u,int v){
mn=n;
mu=u;
mv=v;
mCV = new CVertex[n];
for(int i=0;i<mn;i++)
mCV[i].SetNo(i);
}
void ShowPath(int len,int *path)
{
cout<<"一条路径：";
for(int i=0;i<=len;i++)
cout<<path[i]<<" ";
cout<<endl;
}
/*
void youhua(){
}
*/
public:
CGraph(int n,int m,const int* e,int u,int v){
MySet(n,u,v);
for(int i=0;i<m;i++){
mCV[e[i*2]].AddDegree(e[i*2+1]);
mCV[e[i*2+1]].AddDegree(e[i*2]);
}
}
CGraph(int n,int** Matrix,int u,int v){
MySet(n,u,v);
}
~CGraph(){
delete []mCV;
}
void Show(){
cout<<"\n\n 显示图："<<" 顶点数："<<mn<<endl;
for(int i=0;i<mn;i++)
mCV[i].Show();
cout<<"\n求顶点 "<<mu<<" , "<<mv<<" 间的路径数"<<endl;
cout<<"显示完毕！！"<<endl;
}
int solve();
};
int CGraph::solve()
{
int *path = new int [mn];
int len = 0;
path[0] = mu;
int paths = 0;
do{
if(!mCV[path[len]].SetCurNext()){//无路可走
mCV[path[len]].SetCurHead();
len --;
}
else{//路径的下一个顶点
int tmp = mCV[path[len]].GetCurNode()->mNo;
bool bGo = false;
for(int i=0;i<=len;i++){
if(path[i] == tmp){
bGo = true;
break;
}
}
if (bGo)
continue;
len++;
path[len] = tmp;
if(path[len] == mv){//到达终点
// ShowPath(len,path);
paths ++;
len --;
}
}
}while(len>=0);
return paths;
}
void solve(int n, int m, const int *e, int u, int v)
{
CGraph cg(n,m,e,u,v);
cg.Show();
cout<<cg.solve()<<endl<<endl;
}
15 楼
小黑骑DK [专家分：610] 发布于 2007-04-14 16:53:00
/*
C 语言编译器编译
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define BASE 1000000000//10e9
#define SIZE 5
typedef struct
{
int data;//用来存放顶点值(const int *e里的值)
unsigned long routeNum[SIZE];//用来存放此点到源点的路径数
}POINT;
//大数乘2
void multiple(unsigned long *p)
{
unsigned long temp = 0;
int i = SIZE - 1;
while (i >= 0)
{
temp += (2 * p[i]);
if (temp > BASE)
{
p[i] = (temp % BASE);
temp /= BASE;
}
else
{
p[i] = temp;
break;
}
i--;
}
}
//大数相加
void add(unsigned long *p, unsigned long *sum)
{
unsigned long temp = 0;
int i = SIZE - 1;
while (i >= 0)
{
temp += (p[i] + sum[i]);
if (temp > BASE)
{
sum[i] = (temp % BASE);
temp /= BASE;
}
else
{
sum[i] = temp;
break;
}
i--;
}
}
//显示大数
void print(unsigned long *p)
{
int index = 0;
while (p[index] == 0 && index < SIZE - 1)
{
index++;
}
printf("%u",p[index++]);
while (index < SIZE)
{
if (p[index] < 10)
{
printf("00000000");
}
else if (p[index] < 100)
{
printf("0000000");
}
else if (p[index] < 1000)
{
printf("000000");
}
else if (p[index] < 10000)
{
printf("00000");
}
else if (p[index] < 100000)
{
printf("0000");
}
else if (p[index] < 1000000)
{
printf("000");
}
else if (p[index] < 10000000)
{
printf("00");
}
else if (p[index] < 100000000)
{
printf("0");
}
printf("%u",p[index++]);
}
}
//判断num是否在pStore里面.若是返回其下标,否则-1
int in_POINT(int num, POINT *pStore, int stop)
{
int i = 0;
while (i < stop)
{
if (num == pStore[i++].data)
{
return i-1;
}
}
return -1;
}
int in_found(int num, const int *pFound,int posStop)
{
int i = 0;
while (i < posStop)
{
if (num == pFound[i++])
{
return i-1;
}
}
return -1;
}
int save_found(int unsave, const POINT *pStore, int storeStop, int *pFound, int foundStop)
{
int i = 0;
while (i < storeStop)
{
if (unsave != pStore[i].data)//unsave是不想存入的点
{
pFound[foundStop++] = pStore[i].data;
}
i++;
}
return foundStop;
}
16 楼
小黑骑DK [专家分：610] 发布于 2007-04-14 16:54:00
//edge中搜索store[storePos].data的邻接点,并将其信息存入temp中
int search_adjacency(const int *edge, int m, POINT *store, int storePos,
const int *pFound, int foundStop, POINT *temp, int v)
{
int i = 0;
int tempPos = 0;
int index1, index2;
while (i < m)//所有不在found中且与store[storePos]邻接的点都存入temp中
{
if (edge[2*i] == store[storePos].data)
{
if (in_found(edge[2*i+1],pFound,foundStop) == -1)
{
temp[tempPos].data = edge[2*i+1];
memcpy(temp[tempPos++].routeNum, store[storePos].routeNum,
SIZE*sizeof(unsigned long));
}
}
if (edge[2*i+1] == store[storePos].data)
{
if (in_found(edge[2*i],pFound,foundStop) == -1)
{
temp[tempPos].data = edge[2*i];
memcpy(temp[tempPos++].routeNum, store[storePos].routeNum,
SIZE*sizeof(unsigned long));
}
}
i++;
}
for (i=0; i<m; i++)
{
if (edge[2*i] != v && edge[2*i+1] != v)
{
index1 = in_POINT(edge[2*i],temp,tempPos);
if (index1 != -1)
{
index2 = in_POINT(edge[2*i+1],temp,tempPos);
if (index2 != -1)
{
multiple(temp[index1].routeNum);
multiple(temp[index2].routeNum);
}
}
}
}
return tempPos;
}
17 楼
小黑骑DK [专家分：610] 发布于 2007-04-14 16:54:00
void solve(int n, int m, const int *e, int u, int v)//题目确保u,v在图内，所以不判断
{
if (u == v)
{
printf("\nnumbers of routes from %d to %d is: 0\n", u, v);;
return ;
}
else
{
int *pFound = (int *)malloc(sizeof(int) * n);//用来记录已经访问过的点数
int foundStop = 1;//pFound数组的停止的位置,因为u已知，所以从1开始.v是最后存入
POINT *begin = (POINT *)malloc(sizeof(POINT) * (n-1));//记录从u出发所访问的邻接点
POINT *temp = (POINT *)malloc(sizeof(POINT) * (n-1));//临时存放点,存完后拷到begin中
int beginStop = 0, tempStop = 0;//begin,temp数组停止的位置
int beginPos = 0;
int i = 0;
unsigned long sum[SIZE] = {0};//记录总的路径数
memset(begin, 0, sizeof(POINT)*(n-1));
memset(temp, 0, sizeof(POINT)*(n-1));
pFound[0] = u;
//搜索与u相邻的点，并将信息填入begin数组中
while (i < m)
{
if (e[2*i] == u)
{
begin[beginPos].data = e[2*i+1];
begin[beginPos++].routeNum[SIZE - 1] = 1;
}
if (e[2*i+1] == u)
{
begin[beginPos].data = e[2*i];
begin[beginPos++].routeNum[SIZE - 1] = 1;
}
i++;
}
beginStop = beginPos;
for (i=0; i<m; i++)
{
if (e[2*i] != v && e[2*i+1] != v)//包含v的边不能*2
{
int index1 = in_POINT(e[2*i],begin,beginStop);
if (index1 != -1)
{
int index2 = in_POINT(e[2*i+1],begin,beginStop);
if (index2 != -1)
{
begin[index1].routeNum[SIZE - 1] = 2;
begin[index2].routeNum[SIZE - 1] = 2;
}
}
}
}
//判断v是否在begin中,在就记录总和,不在就将begin.data存入found中
if ( (i = in_POINT(v,begin,beginStop)) != -1)
{
add(begin[i].routeNum,sum);
}
//将不是v的点存入found中
foundStop = save_found(v,begin,beginStop,pFound,foundStop);
//搜索与begin数组中相邻的点,并将信息填入temp.完后，将temp拷到begin中,开始下一次搜索
while ( (foundStop < (n - 1)) && (beginStop != 0) )//found中最后一个元素是v,并且begin中有元素
{
for (beginPos=0; beginPos<beginStop; beginPos++)
{
if (begin[beginPos].data != v)//与v邻接的点不用计算
{
tempStop += search_adjacency(e,m,begin,beginPos,pFound,
foundStop,temp+tempStop,v);
}
}
//copy到begin中
memcpy(begin,temp,tempStop*sizeof(POINT));
beginStop = tempStop;
tempStop = 0;
//判断v是否在begin中,在就记录总和,不在就将begin.data存入found中
if ( (i = in_POINT(v,begin,beginStop)) != -1)
{
add(begin[i].routeNum,sum);
}
//将不是v的点存入found中
foundStop = save_found(v,begin,beginStop,pFound,foundStop);
}
//释放资源，结束
free(pFound);
free(begin);
free(temp);
printf("num of routes from %d to %d is: ", u,v);
print(sum);
putchar('\n');
}
}
int main(void)
{
int e[16] = {0,1, 1,2, 2,0, 3,4, 4,5, 5,3, 2,3, 7,8};
solve(8,8,e,2,3);
return 0;
}
18 楼
crossbow [专家分：150] 发布于 2007-04-14 23:59:00
到点了，嗯
我来回复
您所在位置：