結果
問題 | No.483 マッチ並べ |
ユーザー |
![]() |
提出日時 | 2017-02-10 22:33:30 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 1,700 bytes |
コンパイル時間 | 1,550 ms |
コンパイル使用メモリ | 163,628 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-29 08:06:35 |
合計ジャッジ時間 | 3,393 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;} struct bipartite_matching{ static const int MAX_V=22222; vector<int>G[MAX_V]; int match[MAX_V]; bool used[MAX_V]; void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } bool dfs(int v){ used[v]=true; for(int i=0;i<G[v].size();i++){ int u=G[v][i],w=match[u]; if(w<0||!used[w]&&dfs(w)){ match[v]=u; match[u]=v; return true; } } return false; } int matching(){ int res=0; memset(match,-1,sizeof(match)); for(int v=0;v<MAX_V;v++){ if(match[v]<0){ memset(used,0,sizeof(used)); if(dfs(v))res++; } } return res; } }; signed main(){ bipartite_matching latte; int N;cin>>N; rep(i,N){ int a,b,c,d; cin>>a>>b>>c>>d; a--;b--;c--;d--; latte.add_edge(10000+i,a*100+b); latte.add_edge(10000+i,c*100+d); } if(latte.matching()==N){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } return 0; }