結果
問題 | No.8107 Listening |
ユーザー |
![]() |
提出日時 | 2024-03-07 05:18:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,160 bytes |
コンパイル時間 | 6,678 ms |
コンパイル使用メモリ | 434,212 KB |
最終ジャッジ日時 | 2025-02-20 01:37:22 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 TLE * 1 -- * 9 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <deque>#include <queue>#include <string>#include <iomanip>#include <set>#include <unordered_set>#include <map>#include <unordered_map>#include <utility>#include <stack>#include <random>#include <complex>#include <functional>#include <stdio.h>#include <stdlib.h>#include <time.h>#include <math.h>#include <assert.h>#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endif#if __has_include(<boost/multiprecision/cpp_int.hpp>)#include <boost/multiprecision/cpp_int.hpp>using cpp_int=boost::multiprecision::cpp_int;#endif#if __has_include(<boost/multiprecision/cpp_dec_float.hpp>)#include <boost/multiprecision/cpp_dec_float.hpp>template<unsigned size>using cpp_float=boost::multiprecision::number<boost::multiprecision::cpp_dec_float<size>>;template<unsigned size>using cpp_double=boost::multiprecision::number<boost::multiprecision::cpp_dec_float<size,long long>>;#endifusing namespace std;using ll=long long;#define read(x) cin>>(x);#define readll(x) ll (x);cin>>(x);#define readS(x) string (x);cin>>(x);#define readvll(x,N) vector<ll> (x)((N));for(int i=0;i<(N);i++){cin>>(x)[i];}#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)#define rep2d(i,j,H,W) for(ll (i)=0;(i)<(H);(i)++)for(ll (j)=0;(j)<(W);j++)#define is_in(x,y) (0<=(x) && (x)<H && 0<=(y) && (y)<W)#define yn {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}#define double_out(x) fixed << setprecision(x)template<class T> inline void erase_duplicate(vector<T>& A){sort(A.begin(),A.end());A.erase(unique(A.begin(),A.end()),A.end());}inline ll powll(ll x,ll n){ll r=1;while(n>0){if(n&1){r*=x;};x*=x;n>>=1;};return r;}// https://ei1333.github.io/library/graph/flow/gabow-edmonds.hpp.html// https://qiita.com/Kutimoti_T/items/5b579773e0a24d650bdf/*** @brief Gabow Edmonds(一般グラフの最大マッチング)* @docs docs/gabow-edmonds.md*/struct GabowEdmonds {struct edge {int to, idx;};vector< vector< edge > > g;vector< pair< int, int > > edges;vector< int > mate, label, first;queue< int > que;GabowEdmonds(int n) : g(n + 1), mate(n + 1), label(n + 1, -1), first(n + 1) {}void add_edge(int u, int v) {++u, ++v;g[u].push_back(edge{v, (int) (edges.size() + g.size())});g[v].push_back(edge{u, (int) (edges.size() + g.size())});edges.emplace_back(u, v);}int find(int x) {if(label[first[x]] < 0) return first[x];first[x] = find(first[x]);return first[x];}void rematch(int v, int w) {int t = mate[v];mate[v] = w;if(mate[t] != v) return;if(label[v] < (int)g.size()) {mate[t] = label[v];rematch(label[v], t);} else {int x = edges[label[v] - g.size()].first;int y = edges[label[v] - g.size()].second;rematch(x, y);rematch(y, x);}}void assign_label(int x, int y, int num) {int r = find(x);int s = find(y);int join = 0;if(r == s) return;label[r] = -num;label[s] = -num;while(true) {if(s != 0) swap(r, s);r = find(label[mate[r]]);if(label[r] == -num) {join = r;break;}label[r] = -num;}int v = first[x];while(v != join) {que.push(v);label[v] = num;first[v] = join;v = first[label[mate[v]]];}v = first[y];while(v != join) {que.push(v);label[v] = num;first[v] = join;v = first[label[mate[v]]];}}bool augment_check(int u) {que = queue< int >();first[u] = 0;label[u] = 0;que.push(u);while(!que.empty()) {int x = que.front();que.pop();for(auto e : g[x]) {int y = e.to;if(mate[y] == 0 && y != u) {mate[y] = x;rematch(x, y);return true;} else if(label[y] >= 0) {assign_label(x, y, e.idx);} else if(label[mate[y]] < 0) {label[mate[y]] = x;first[mate[y]] = y;que.push(mate[y]);}}}return false;}vector< pair< int, int > > max_matching() {for(int i = 1; i < (int)g.size(); i++) {if(mate[i] != 0) continue;if(augment_check(i)) label.assign(g.size(), -1);}vector< pair< int, int > > ret;for(int i = 1; i < (int)g.size(); i++) {if(i < mate[i]) ret.emplace_back(i - 1, mate[i] - 1);}return ret;}};struct pair_hash{inline size_t operator()(const pair<ll,ll>& p)const{return 10'000'000LL*p.first+p.second;}};int main(){ll N,M;cin>>N>>M;GabowEdmonds GE(N);unordered_map<ll,ll> index;vector<pair<ll,ll>> Edges(M);for(ll i=0;i<M;i++){cin>>Edges[i].first>>Edges[i].second;Edges[i].first--;Edges[i].second--;GE.add_edge(Edges[i].first,Edges[i].second);}auto res=GE.max_matching();unordered_set<pair<ll,ll>,pair_hash> ans(res.begin(),res.end());cout<<ans.size()<<endl;for(ll i=0;i<M;i++){if(ans.find(Edges[i])!=ans.end() || ans.find(make_pair(Edges[i].second,Edges[i].first))!=ans.end()){cout<<i+1<<endl;}}}