emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
250分模拟题 SalesRouting

Problem Statement

     You want to send a group of salespeople from location 0 to location 1, but no two of them can travel through the same location (other than 0 and 1). This removes the possibility of trying to sell a customer the same product twice. Character j of element i (both 0-based) of adj denotes whether locations i and j are connected by a symmetric link ('1' for connected, '0' otherwise). Return the greatest number of salespeople that can be sent. The constraints will guarantee that locations 0 and 1 do not share a link.

Definition

    
Class: SalesRouting
Method: howMany
Parameters: String[]
Returns: int
Method signature: int howMany(String[] adj)
(be sure your method is public)
    

Constraints

- adj will contain between 3 and 12 elements, inclusive.
- Each element of adj will contain exactly N characters, where N is the number of elements in adj.
- Each character in adj will be '0' (zero) or '1' (one).
- Character i of element j of adj will be the same as character j of element i.
- Character i of element i of adj will be '0'.
- Character 1 of element 0 of adj will be '0'.

Examples

0)
     
{
"001",
"001",
"110"
}
 
Returns: 1
We can send a single salesperson from location 0 to location 2, and finally to location 1.
1)
     
{
"0010",
"0010",
"1100",
"0000"
}
 
Returns: 1
Same as before, but now there is an isolated location 3.
2)
     
{
"001100",
"000001",
"100010",
"100010",
"001101",
"010010"
}
 
Returns: 1
The only location that is directly connected to location 1 is 5, so only 1 salesperson can be sent.
3)
     
{
"001111",
"001111",
"110000",
"110000",
"110000",
"110000"
}
 
Returns: 4
4)
     
{
"00000",
"00000",
"00000",
"00000",
"00000"
}
 
Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2006-09-05 10:19 emu 阅读(2010) 评论(4)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: 250分模拟题 SalesRouting 2006-09-05 19:29 frog
public class SalesRouting {

public int howMany(String[] adj) {
int rowCount = adj.length;
int cellCount = adj[0].length();
int[] m = new int[cellCount];
//先看看Location0＆1有没有直接连同的，就是只通过一个Location就到
//等于2的就是可行的通道
for(int i=2; i<cellCount; i++){
if(adj[0].charAt(i) == '1')
m[i] += 1;
if(adj[1].charAt(i) == '1')
m[i] += 1;
}
//只搜索右上的三角，用m[]表示连通状态，现在m是Location0＆1的连通状态
//0表示同0＆1的不连通，1表示连通，2表示有通路。
//用m1表示剩下的Location的连通状态
for(int j=2; j<rowCount; j++){
//for(int k=0; k<rowCount; k++)
// System.out.print(m[k]+" ");
//System.out.println(" ");
//这里判断m[]==1非常重要，
//m[]==0就是集合不连通，m[]==2就是已经连通，不需要再判断了
if(m[j] == 1){
for(int i=j; i<cellCount; i++){
if((adj[j].charAt(i) == '1') && (m[i] != 2)){
m[i]++;
}
}
}
}

//计数
int result = 0;
for(int i=2; i<cellCount; i++){
if(m[i] == 2)
result++;
}

return result;
}

public static void main(String[] args) {
SalesRouting sr = new SalesRouting();

int result = sr.howMany(new String[]{"001","001","110"});
System.out.println(result);
result = sr.howMany(new String[]{"0010","0010","1100","0000"});
System.out.println(result);
result = sr.howMany(new String[]{"001100","000001","100010","100010","001101","010010"});
System.out.println(result);
result = sr.howMany(new String[]{"001111","001111","110000","110000","110000","110000"});
System.out.println(result);
result = sr.howMany(new String[]{"00000","00000","00000","00000","00000"});
System.out.println(result);
}
}   回复  更多评论
  

# re: 250分模拟题 SalesRouting 2006-09-05 19:30 frog
500合1000的还没做出来，
1000的我感觉好难，不知有谁已经成功了  回复  更多评论
  

# re: 250分模拟题 SalesRouting 2006-09-05 19:53 bood
500的用DP求出所有子串是否回文即可
1000的没做出来，不过看到有人直接用公式2^(a+b)+2^c次……汗
frog我倒是250的看不懂你的解法，这样肯定能保证最大么？  回复  更多评论
  

# re: 250分模拟题 SalesRouting 2008-07-14 22:08 mabusyao
package salesRouting;

public class SalesRouting {

public static int howMany(String[] adj) {
matrix = new int[adj.length][adj[0].length()];
flags = new int[adj.length];

for(int i = 0; i < adj.length; i++) {
flags[i] = 0;
for(int j = 0; j < adj[0].length(); j++) {
matrix[i][j] = adj[i].charAt(j) - 48;

}
}

return iterate(0);
}

private static int[][] matrix;
private static int[] flags;
private static int iterate(int index) {
int result = 0;
if(index == 1) {
System.out.print(index+ " ");
return 1;
}

int next = 1;
while(next < matrix.length) {
if(matrix[index][next] == 1 && flags[next] == 0 && flags[index] == 0) {
if(index != 0 && index != 1) flags[index] = 1;
int success = iterate(next);
if (success == 1) {
if(index == 0) {
System.out.println(0 + " ");
} else System.out.print(index+ " ");
result++;
}else flags[index] = 0;
}
next++;
}
return result;
}
}



到底该怎么保证最大呢？ 我找了个例子：
String[] str={"001100","000011","100110","101001","011000","010100"};

想了半天没有想出来该怎么保证结果是最大。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: