MatsuLab. Lecture Note/sougouenshu2007/round2/2 のバックアップ(No.2)

第２回 †

問題として与えられる無向グラフG(V, E)中のノード(偶数個)を2つのノード集合LおよびRに等分する分割方法を求める。ただし、

問題として与えられるグラフ情報は以下のように与えられる。

ノードID (X座標, Y座標) 隣接するノード数　隣接するノードID...

書式

int GetProblem(const int problem_number, char **filename, char *key);

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

書式

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が返される．

上記の問題に取り組む。