← 返回题目列表

AtCoder · joisc2011_joitter

joitter. 乔伊特

中文机器翻译题面 查看原题

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

ジョイッター (Joitter) - 原题 PDF 第 1 页
原题PDF第6页
ジョイッター (Joitter) - 原题 PDF 第 2 页
原题PDF第7页
ジョイッター (Joitter) - 原题 PDF 第 3 页
原题PDF第8页
可复制的 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