以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 1 – Joitter
ジョイッター(Joitter)
ジョイッター(Joitter) は,短い日記の気軽な投稿や写真の共有を通して,知り合いとのインターネット上
でのコミュニケーションをより快適にする,話題沸騰中のソーシャル・ネットワーキング・サービス(SNS)
である.
ジョイッターでは,自分以外のユーザを「友人」というリストに登録することができる.あるユーザA
があるユーザB を「友人」として登録しようとすると,ユーザB に通知が届く.ユーザB がこれに許可す
ることで,2 人は互いに「友人」として登録される.これを1 回の「友人」登録と考える.「友人」登録に
は,なぜか2 人のユーザに依存したコストがかかる.ユーザA とユーザB が互いに「友人」でありユーザ
B とユーザC が互いに「友人」であっても,ユーザA とユーザC が互いに「友人」となるとは限らない.
ジョイッターでは,ユーザは日記の公開設定を以下の3 種類のいずれかに設定できる.
(1) 「友人」にのみ公開する.
(2) 「友人」あるいは「友人」の「友人」であるユーザにのみ公開する.
(3) 「友人」関係を辿って到達できるユーザにのみ公開する.
N 人が新しくジョイッターに登録した.日記の公開設定として各々が上記の(1), (2), (3) のいずれかを選
んだ.偶然にも,N 人の中でちょうど1 人だけが選んだ公開設定は存在しなかった.
現在,N 人の間の「友人」関係は全く登録されていない.N 人全員が他の全員の日記を読めるようにな
るには,最小で何回の「友人」登録が必要であろうか.また,最小回数の「友人」登録でこれを達成する
ための最小のコストはいくらになるだろうか.
課題
N 人の日記の公開設定と,各2 人の組が「友人」として登録されるためのコストが与えられたとき,N
人全員が他の全員の日記を読めるようになるための「友人」登録の回数の最小値と,その回数を実現する
最小のコストを求めるプログラムを作成せよ.
制限
2 ≦N ≦1 000 ユーザの人数
1 ≦Cij ≦1 000 (i , j) 「友人」登録のためのコスト
入力
標準入力から以下の入力を読み込め.
ジョイッター– 1 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 1 – Joitter
• 1 行目には整数N が書かれており,ユーザの人数を表す.ユーザには1 からN までの番号がつけら
れている.
• 続くN 行には各ユーザの日記の公開設定が書かれている.1 + i 行目(1 ≦i ≦N) には,ユーザi の日
記の公開設定を表す1 つの整数が書かれている.この整数は1, 2, 3 のいずれかであり,公開設定(1),
(2), (3) のそれぞれに対応する.どのユーザに対しても,他の誰かとは同じ公開設定になっているこ
とが保証されている.
• 続くN 行には「友人」登録のためのコストが書かれている.1 + N + i 行目(1 ≦i ≦N) にはN 個の整
数が空白を区切りとして書かれており,そのうちのj 番目(1 ≦j ≦N) の整数Cij は,ユーザi とユー
ザj が友人として登録されるためのコストを表す.任意のi, j に対してCii = 0 およびCij = C ji を満
たす.
出力
標準出力に,N 人全員が全員の日記を読めるようになるための「友人」登録の回数の最小値と,その回
数を実現する最小のコストを表す2 つの整数を,空白を区切りとして1 行に出力せよ.
ジョイッター– 2 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 1 – Joitter
入出力の例
入力例1 出力例1
7 15 62
1
3
2
1
3
1
2
0 5 2 1 6 3 2
5 0 1 5 2 4 8
2 1 0 3 4 1 1
1 5 3 0 4 9 5
6 2 4 4 0 6 2
3 4 1 9 6 0 6
2 8 1 5 2 6 0
入力例2 出力例2
5 4 20
2
2
3
2
3
0 2 1 9 9
2 0 8 4 6
1 8 0 7 5
9 4 7 0 8
9 6 5 8 0
入力例3 出力例3
3 2 15
3
3
3
0 8 7
8 0 9
7 9 0
ジョイッター– 3 / 3