[[MatsuLab. Lecture Note/sougouenshu2007/round2]]

* 第２回 [#a16fbc8d]
** 問題 [#d722df8e]
問題として与えられる無向グラフG(V, E)中のノード(偶数個)を2つのノード集合LおよびRに等分する分割方法を求める。ただし、
- 分割後に生成されるノード集合LおよびRに続するノード数は同じでなければならない。
- 異なるノード集合にまたがるエッジ数がより少ない分割方法を良い解と定義する。~

問題として与えられるグラフ情報は以下のように与えられる。
 ノードID (X座標, Y座標) 隣接するノード数　隣接するノードID...
- ノードID: ノードの識別子で、データファイル内では１から始まり、１ずつ増えていく。
- (X座標,Y座標): ２次元空間内におけるノードの位置を表す。
- 隣接するノード数: ノードからエッジによって結ばれているノードの個数。どのノードとも結ばれていない場合,0となる。
- 隣接するノードID: 隣接する各ノードのノードID。隣接するノード数に依存するため、可変個となる。

出典 : [[Grid Challenge 2006:http://www.hpcc.jp/sacsis/2006/grid-challenge/]]

** 問題を解くために用意されているAPI [#v02b5588]
*** 問題取得用API [#v0aabfb2]
- 書式~
 int GetProblem(const int problem_number, char **filename, char *key);
- 概要~
プログラムは開始時にGetProblem()を呼ぶことにより，データファイルの場所とキー文字列を取得する必要がある．~
全プロセスを通して一つのプロセスのみがGetProblem()を呼ぶこと.~
- 引数と戻り値~
-- problem_number : 問題番号を指定する．
-- filename : データファイルの場所を示す文字列へのポインタが*filenameに返される．
-- key : キー文字列がkeyから始まる領域に返される．
-- return value : 正常に終了した場合は0，そうでない場合は1が返される．

*** 解答用API [#sbbe36bc] 
- 書式~
 int AnswerProblem(const int problem_number, const char *key, const int *belong_to, int *out_edge_cnt, double *elapsed_time, char *check_string);
- 概要~
プログラムは計算結果を引数としてAnswerProblem()に渡し，解答に関する情報(集合間の枝の本数，経過時間，終了時刻，解答チェック用文字列)を取得する． GetProblem()を呼び出したプロセスのみがAnswerProblem()を呼び出すことができる．
- 引数と戻り値~
-- problem_number: 問題番号を指定する． 
-- key: キー文字列へのポインタを指定する． 
-- belong_to: グラフ内のノードの所属情報を指定する．例えばノード数が500の場合，配列 belong_to[1]〜[500] に所属する集合(1または2)を格納する．インデックスが1から始まることに注意． 
-- out_edge_cnt: 引数として渡された配列 belong_to を用いてAnswerProblem()が計算した集合間の枝の本数へのポインタが返される． 
-- elapsed_time: GetProblem() 呼び出し以降の経過時間(ミリ秒単位)へのポインタが返される． 
-- check_string: 解答チェック用文字列がcheck_stringから始まる領域に返される． 
-- return value: 正常に終了した場合は0，そうでない場合は1が返される．
** 課題 [#ia78732f]
上記の問題に取り組む。

* [#j05937b1]
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS