查看: 2962| 回复: 17
跳转到指定楼层
上一主题 下一主题
收起左侧

请大牛帮我看一个关于欧拉路径的ZOJ题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 garry 于 2011-3-1 20:13 编辑

最近连续被UCLA,UW,JHU拒了之后心情极其郁闷,想排解一下,所以在ZJU上做ACM ICPC的题,遇到一道关于找欧拉路径的题,写完之后提交上去竟然是Output limitation exceeded...怎么找也不知道问题出在哪儿,希望大牛帮我看看。题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1919
我的源程序在附件中。 1919.rar (1.12 KB, 下载次数: 6)
(问题貌似已解决,感谢暗影吉他手、epic、darksteel)

上一篇:IC设计模拟,射频方面有那几家学校和教授比较强的呢
下一篇:Austin的EE实力怎么样?
🔗
bignews 2011-3-1 11:08:32 | 只看该作者
全局:
汗……这个版变成acm版了么……

算法盲帮顶
回复

使用道具 举报

🔗
 楼主| garry 2011-3-1 12:10:12 | 只看该作者
全局:
2# 暗影吉他手
原来是校友帮顶啊。。对了,你认识许多吧?
回复

使用道具 举报

🔗
epic 2011-3-1 13:18:33 | 只看该作者
全局:
我贴个浙大的模板,lz你自己借鉴一下吧
//求欧拉回路或欧拉路,邻接阵形式,复杂度O(n^2)
//返回路径长度,path返回路径(有向图时得到的是反向路径)
//传入图的大小n和邻接阵mat,不相邻点边权0
//可以有自环与重边,分为无向图和有向图

#define MAXN 100

void find_path_u(int n,int mat[][MAXN],int now,int& step,int* path){
        int i;
        for (i=n-1;i>=0;i--)
                while (mat[now][i]){. 1point 3 acres
                        mat[now][i]--,mat[i][now]--;
                        find_path_u(n,mat,i,step,path);
                }
        path[step++]=now;. check 1point3acres for more.
}
.1point3acres
void find_path_d(int n,int mat[][MAXN],int now,int& step,int* path){
        int i;
        for (i=n-1;i>=0;i--).--
                while (mat[now][i]){
                        mat[now][i]--;
                        find_path_d(n,mat,i,step,path);
                }
        path[step++]=now;.google  и
}
-baidu 1point3acres
int euclid_path(int n,int mat[][MAXN],int start,int* path){. Waral dи,
        int ret=0;
        find_path_u(n,mat,start,ret,path);.
//        find_path_d(n,mat,start,ret,path);
        return ret;
}
回复

使用道具 举报

🔗
darksteel 2011-3-1 13:34:41 | 只看该作者
全局:
1# garry

看了下楼主的代码,题目中说单词长度1-20,你数组不能正好开20吧。其它不知道有没有问题,但这里几乎肯定会出问题
回复

使用道具 举报

🔗
 楼主| garry 2011-3-1 13:44:19 | 只看该作者
全局:
4# epic
十分感谢!这个欧拉路径应该是不难,可是我却一直找不到自己什么地方错了,都找了好几天了。。。还是希望高手帮我看看我的代码。。
回复

使用道具 举报

🔗
 楼主| garry 2011-3-1 13:48:14 | 只看该作者
全局:
5# darksteel . .и
是这个错误吗,我开的大点试试,不过这次错误的名字叫:output limitation exceeded,第一次遇见。我在网上查说有可能是什么地方死循环了,我反复读了好多遍自己的代码,不知道什么地方可以引起死循环。最重要的是手里没有测试数据,更不知道啥地方错了。。。
回复

使用道具 举报

🔗
darksteel 2011-3-1 14:10:40 | 只看该作者
全局:
7# garry

额,你的代码我数组开到22能过。你试试
回复

使用道具 举报

🔗
 楼主| garry 2011-3-1 16:42:55 | 只看该作者
全局:
8# darksteel
啊?我再试试。。。
回复

使用道具 举报

🔗
 楼主| garry 2011-3-1 17:23:00 | 只看该作者
全局:
8# darksteel
的确是。。。我以前也写过一个程序,也是数组开正好,结果怎么也过不去,开大点儿就过去了。我一直以为是我的代码有问题。难道是zju的测试数据有问题?花了我整两天时间,读了N遍自己写的代码,还郁闷的不得了。。。

非常感谢darksteel!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表