結果
問題 | No.2403 "Eight" Bridges of Königsberg |
ユーザー |
![]() |
提出日時 | 2023-08-04 22:27:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 1,293 bytes |
コンパイル時間 | 1,806 ms |
コンパイル使用メモリ | 177,112 KB |
実行使用メモリ | 13,176 KB |
最終ジャッジ日時 | 2024-11-26 17:50:28 |
合計ジャッジ時間 | 3,903 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N, M; cin >> N >> M; vector<vector<int>> E(N); vector<vector<int>> E2(N); for (int i = 0; i < M; i++){ int U, V; cin >> U >> V; U--; V--; E[U].push_back(V); E2[U].push_back(V); E2[V].push_back(U); } int cc = 0; vector<int> c(N, -1); for (int i = 0; i < N; i++){ if (c[i] == -1 && !E2[i].empty()){ c[i] = cc; queue<int> Q; Q.push(i); while (!Q.empty()){ int v = Q.front(); Q.pop(); for (int w : E2[v]){ if (c[w] == -1){ c[w] = c[v]; Q.push(w); } } } cc++; } } vector<int> in(N, 0), out(N, 0); for (int i = 0; i < N; i++){ for (int j : E[i]){ out[i]++; in[j]++; } } if (cc == 1){ int a = 0; for (int i = 0; i < N; i++){ a += abs(in[i] - out[i]); } if (a == 0){ cout << 0 << endl; } else { cout << (a - 2) / 2 << endl; } } else { vector<int> D(cc, 0); for (int i = 0; i < N; i++){ if (!E2[i].empty()){ D[c[i]] += abs(in[i] - out[i]); } } int ans = 0; for (int i = 0; i < cc; i++){ ans += max(D[i], 2); } cout << (ans - 2) / 2 << endl; } }