返回   cpper编程论坛 > 算法
注册账号 论坛帮助 会员列表 日历事件 搜索 今日新帖 标记版面已读

回复
 
LinkBack 主题工具 显示模式
  #1 (permalink)  
旧 2006-04-17
普通会员
 
注册日期: 2006-03-28
帖子: 61
colinzhengj 正向着好的方向发展
默认 也出个图论题

自己编的,呵呵
城市间有公路相连。如果一个城市和K个城市相连,这个城市的“等级”为K。
小明幻想自己是执政者。他想要至少一个等级为A1的城市,至少一个等级为A2的城市……至少一个等级为An的城市。其他等级的城市都不要。
1<=Ai<=m。
请帮他设计这样一张地图并给出时间复杂度(关于m和n)

附加问题:设计一个算法使地图上的城市数最小。不是什么NP hard问题
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #2 (permalink)  
旧 2006-04-19
Elminster 的头像
超级版主
 
注册日期: 2002-09-09
帖子: 1,763
Elminster 正向着好的方向发展
默认

引用:
作者: colinzhengj
自己编的,呵呵
一个国家的一些城市间有公路相连。如果有K条公路通向一个城市,这个城市的“等级”为K。
小明幻想自己是执政者。他想要至少一个等级为A1的城市,至少一个等级为A2的城市……至少一个等级为An的城市。其他等级的城市都不要。
1<=Ai<=m。
请帮他设计这样一张地图并给出时间复杂度(关于m和n)
你忘了说有向图还是无向图 ……
嗯嗯,这个题目还是有点意思的,至少不需要太多的背景知识就能做,大家有兴趣的话可以来看看。
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #3 (permalink)  
旧 2006-04-19
普通会员
 
注册日期: 2006-03-28
帖子: 61
colinzhengj 正向着好的方向发展
默认

无向的。不好意思,有向的我也不知道怎么做
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #4 (permalink)  
旧 2006-04-19
普通会员
 
注册日期: 2006-03-08
帖子: 31
Juvexp 正向着好的方向发展
默认

生成的图是不是要连通的?
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #5 (permalink)  
旧 2006-04-19
普通会员
 
注册日期: 2006-03-28
帖子: 61
colinzhengj 正向着好的方向发展
默认

题目描述改的清楚了一点。不需要连通,是simple graph
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #6 (permalink)  
旧 2006-04-25
Elminster 的头像
超级版主
 
注册日期: 2002-09-09
帖子: 1,763
Elminster 正向着好的方向发展
默认

这题不难吧?为什么没人做?
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #7 (permalink)  
旧 2006-04-26
wqqafnd 的头像
高级会员
 
注册日期: 2004-10-08
帖子: 193
文章: 1
wqqafnd 正向着好的方向发展
发送 MSN 消息给 wqqafnd
默认

引用:
作者: colinzhengj
自己编的,呵呵
城市间有公路相连。如果一个城市和K个城市相连,这个城市的“等级”为K。
小明幻想自己是执政者。他想要至少一个等级为A1的城市,至少一个等级为A2的城市……至少一个等级为An的城市。其他等级的城市都不要。
1<=Ai<=m。
请帮他设计这样一张地图并给出时间复杂度(关于m和n)

附加问题:设计一个算法使地图上的城市数最小。不是什么NP hard问题
最简单的一种实现:
C++ 代码:
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. struct Road{
  7.     int left;
  8.     int right;
  9.     Road(int l,int r):left(l),right(r){}
  10. };
  11.  
  12. int main(){
  13.     const int N = 10;      //number of cities
  14.     const int Level&#91;N] = {1,2,2,3,4,2,4,5,3,2}; //0 < Level[i] < N
  15.  
  16.     int city&#91;N] = {0};
  17.     vector<Road> road;
  18.  
  19.     for(int i = 0;i < N;++i){
  20.         for(int j = i + 1;j < N;++j){
  21.             if(city&#91;i] == Level[i])
  22.                 break;
  23.             else if(city&#91;j] == Level[j])
  24.                 continue;
  25.             else{
  26.                 road.push_back(Road(i,j));
  27.                 ++city&#91;i];
  28.                 ++city&#91;j];
  29.             }
  30.         }
  31.         if(city&#91;i] < Level[i]){
  32.             cout<<"Cannot solve the problem!\n";
  33.             break;
  34.         }
  35.     }
  36.  
  37.     for(int i = 0;i < int(road.size());++i)
  38.         cout<<road&#91;i].left<<"---"<<road[i].right<<endl;
  39.     return 0;
  40. }
__________________
I think therefore I am.
——Rene Descartes
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #8 (permalink)  
旧 2006-04-26
普通会员
 
注册日期: 2006-03-28
帖子: 61
colinzhengj 正向着好的方向发展
默认

你理解错题了,城市数目是不知道的。你写的Level应该是一个集合,每个元素表示至少要一个等级为它的城市
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #9 (permalink)  
旧 2006-04-27
wqqafnd 的头像
高级会员
 
注册日期: 2004-10-08
帖子: 193
文章: 1
wqqafnd 正向着好的方向发展
发送 MSN 消息给 wqqafnd
默认

引用:
作者: colinzhengj
你理解错题了,城市数目是不知道的。你写的Level应该是一个集合,每个元素表示至少要一个等级为它的城市
你的意思是Level只给出需要的城市等级,具体的城市个数待定。
那么,Level[i]最小为n,城市数最少为max(Level[i])+1,如果存在。
m应该代表城市数吧?那么Level[i]<m,而不是<=
不知这回理解对没?:O
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #10 (permalink)  
旧 2006-05-20
Elminster 的头像
超级版主
 
注册日期: 2002-09-09
帖子: 1,763
Elminster 正向着好的方向发展
默认

引用:
作者: wqqafnd
你的意思是Level只给出需要的城市等级,具体的城市个数待定。
那么,Level[i]最小为n,城市数最少为max(Level[i])+1,如果存在。
m应该代表城市数吧?那么Level[i]<m,而不是<=
不知这回理解对没?:O
出题人貌似不出现了,俺来接吧:差不多就是你说的那样,问题的输入只有一些城市等级,具体的城市个数待定。“Level[i]最小为n”是不对的,因为有些城市之间可能没路,“城市数最少为max(Level[i])+1”没错。m 也不代表城市数,而是代表等级的一个上限,也就是说任意一个城市的等级不会超过这么多 —— 要加这个上限是因为程序运行的时间和这个有关,在两个城市之间连边可以要花时间的。
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #11 (permalink)  
旧 2006-05-26
普通会员
 
注册日期: 2006-03-28
帖子: 61
colinzhengj 正向着好的方向发展
默认

不好意思一段时间没来看。这道题是我在读有关degree set的一个命题的证明时想的。命题是"城市数只需要max(Level[i])+1”,就是说max(Level[i])+1个城市一定能满足。证明是Kapoor, Polimeni, Wall给出的一个构造性的证明,其构造过程就是一个低复杂度的算法。。。
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
  #12 (permalink)  
旧 2006-06-12
初级会员
 
注册日期: 2006-06-11
帖子: 7
cs_wangpeng 正向着好的方向发展
默认

那是不是一旦有两个城市相连,这两个城市的等级都要加1?正在想,争取独立做出来。
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
回复时引用此帖
回复

书签

主题工具
显示模式

发帖规则
不可以发表新主题
不可以发表回复
不可以上传附件
不可以编辑自己的帖子

启用 BB 代码
论坛启用 表情符号
论坛启用 [IMG] 代码
论坛禁用 HTML 代码
Trackbacks are 启用
Pingbacks are 启用
Refbacks are 启用



所有时间均为格林尼治时间 +9。现在的时间是 09:30 AM


Powered by vBulletin® 版本 3.7.0
版权所有 ©2000 - 2008,Jelsoft Enterprises Ltd.
(C) Copy Right All Right Reserved 2001 - 2007

Search Engine Friendly URLs by vBSEO 3.1.0