对路冲的讨论不少。墓地旁边的房子呢？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

对路冲的讨论不少。墓地旁边的房子呢？

对路冲的讨论不少。墓地旁边的房子呢？# Living

p*22012-07-23 07:07

1 楼

一个无向图，有n个vertices
每个vertice 用一个color来表示， color用int来表示
现在对于某种color来说，会对应几个点，如果这些点的邻居的color是不同的颜色，则
认为这两种不同的color有relation
那么现在求有最多relation的color，如果两种color的reliation数目一样多，则应该
选择color的int值更小的那个

b*r2012-07-23 07:07

2 楼

看见一open house,什么都好，就是后院紧靠一墓地。不知是公墓
，还是私墓。整个墓地只有房子lot的1/2大。
老中好象很在乎这个。老美呢？

l*82012-07-23 07:07

3 楼

My two cents:
遍历所有边，把color-color relations 存在multimap里面。
最后扫描multimap找出relation最多的color.

【在 p*****2 的大作中提到】

: 一个无向图，有n个vertices
: 每个vertice 用一个color来表示， color用int来表示
: 现在对于某种color来说，会对应几个点，如果这些点的邻居的color是不同的颜色，则
: 认为这两种不同的color有relation
: 那么现在求有最多relation的color，如果两种color的reliation数目一样多，则应该
: 选择color的int值更小的那个

k*n2012-07-23 07:07

4 楼

明显不介意。。
比如取名字，，老美爱把爷爷奶奶的名字做小孩的名字。
老中是要避讳的。。
所以老中要离祖先远远的。。老美恨不得在地下室放棺材，好长生不老。

p*22012-07-23 07:07

5 楼

这道题就是数据结构题。没什么算法。

【在 l*********8 的大作中提到】

: My two cents:
: 遍历所有边，把color-color relations 存在multimap里面。
: 最后扫描multimap找出relation最多的color.

b*t2012-07-23 07:07

6 楼

我跟有限的几个老美讨论过这个问题，他们好像不在乎。

w*o2012-07-23 07:07

7 楼

HashMap> map = new HashMapInteger>>();
int[] max = new int[n]; // n = total number of colors
for(Vertex v : G.V()) {
for(Vertex w: v.adj()) {
if(w.color != v.color) {
if(map.containsKey(w.color)) {
HashSet set = map.get(w.color);
if(!set.contains(v.color)) {
set.add(v.color);
max[w.color]++;
}
} else {
HashSet set = new HashSet();
set.add(v.color);
map.put(w.color, set);
max[w.color]++;
}
}
}
}
int maxColor = 0;
for(int i = 1; i < n; i++) {
if(max[i] > max[maxColor]) maxColor = i;
}
return maxColor;