JOI2007本戦 D問題P7 「最悪の記者」
問題概要
問題文参照
制約
$ n{\leqq}5000
$ m{\leqq}10^4
解法
難しい。
解けなかった。
というか考えを放棄していた。
ダメだなぁ･･･
与えられている情報について整理する。
すべてのチームに異なる順位がついたとあるので
$ Nチームあるならば
$ N- 1, N-2,..., 1, 0回勝ったチームがそれぞれ$ 1チームずついることになる。
よって、有向辺を引いて、回数のスコアの強い順から考えるのかな？
となって適当に書いたらWA。
そりゃそうだよなぁ･･･(ちゃんとした考察なしにあった試しがない)
与えられた情報である
a<bで$ a位のチームと$ b位のチームで必ず$ a位が勝利した
という大小関係が出ている。
トポロジカルソートでは、優先順位や強さなどの情報がある閉路がない有向グラフにおいて、 条件をみたす、矢印の遷移をみたすノードの選び方を１つ求めるものである。
よって、現在勝っているチームから選んでいく、つまり入次数が0の頂点からトポロジカルソートをすればよい。
このように選べば、右側にあるチームに勝つとすれば、勝つ回数の条件をみたす。
https://gyazo.com/fac8ab8cfb0931e4c22d85b40bf81a32
よって、以上のようにトポロジカルソートをして、順番を求めればいい。
複数解があるかどうかは、Queueのサイズを確かめればいい。
計算量
$ O(N + M)
新たな学び
順位や優先度、大小関係を図るとき、そのようにソートしたい、そのような一例を求めたいときは トポロジカルソートをすればいいことがわかった。 トポロジカルソートは有向グラフかつ、閉路さえなければ、どれだけ辺があってもどれだけなくても「一例」は求めることが出来る。
数え上げはBitDP
反省点
大きさ、優先度、大小関係でトポロジカルソートが出てこないのは反省。。。
考察しないとダメなんだなぁ
完璧な考察が終わるまで実装ダメルールやろう
コード
code: cpp
using LL = long long;
//~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~
constexpr int MAX_V = 5050;
int main() {
int n, m;
cin >> n >> m;
vector<int> in(n, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--, b--;
}
queue<int> Q;
for (int i = 0; i < n; i++) if (ini == 0)Q.push(i); bool multi = false;
vector<int> ans;
while (!Q.empty()) {
int v = Q.front();
Q.pop();
if (Q.size() > 0) multi = true;
ans.push_back(v);
for (int i = 0; i < Gv.size(); i++) { Q.push(to);
}
}
}
for (int i = 0; i < n; i++) cout << ansi + 1 << endl; cout << multi << endl;
return 0;
}