結果
問題 | No.241 出席番号(1) |
ユーザー |
|
提出日時 | 2015-07-08 21:42:43 |
言語 | C++11 (gcc 4.8.5) |
結果 |
AC
|
実行時間 | 4 ms |
コード長 | 943 Byte |
コンパイル時間 | 937 ms |
使用メモリ | 1,548 KB |
最終ジャッジ日時 | 2019-02-04 01:11:58 |
テストケース
テストケース表示入力 | 結果 | 実行時間 使用メモリ |
---|---|---|
challenge01.txt | AC | 2 ms
1,504 KB |
challenge02.txt | AC | 2 ms
1,488 KB |
sample1.txt | AC | 4 ms
1,504 KB |
sample2.txt | AC | 1 ms
1,500 KB |
sample3.txt | AC | 2 ms
1,500 KB |
system_test1.txt | AC | 2 ms
1,512 KB |
system_test2.txt | AC | 3 ms
1,540 KB |
system_test3.txt | AC | 3 ms
1,544 KB |
test1.txt | AC | 3 ms
1,488 KB |
test2.txt | AC | 2 ms
1,484 KB |
test3.txt | AC | 3 ms
1,496 KB |
test4.txt | AC | 1 ms
1,504 KB |
test5.txt | AC | 3 ms
1,500 KB |
test6.txt | AC | 4 ms
1,500 KB |
test7.txt | AC | 2 ms
1,504 KB |
test8.txt | AC | 2 ms
1,524 KB |
test9.txt | AC | 2 ms
1,544 KB |
test10.txt | AC | 2 ms
1,548 KB |
test11.txt | AC | 3 ms
1,548 KB |
test12.txt | AC | 3 ms
1,548 KB |
test13.txt | AC | 2 ms
1,544 KB |
test14.txt | AC | 2 ms
1,548 KB |
test15.txt | AC | 2 ms
1,544 KB |
test16.txt | AC | 3 ms
1,548 KB |
ソースコード
#include <iostream> #include <vector> #include <cstring> using namespace std; int N, A[50]; int V; vector<int> G[100]; int match[100]; bool used[100]; 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 u : G[v]){ int w = match[u]; if(w < 0 || (!used[w] && dfs(w))){ match[v] = u; match[u] = v; return true; } } return false; } int bipartite_matching(){ int res = 0; memset(match, -1, sizeof(match)); for(int v=0;v<V;v++){ if(match[v] < 0){ memset(used, false, sizeof(used)); if(dfs(v)){ ++res; } } } return res; } int main(){ cin >> N; for(int i=0;i<N;i++){ cin >> A[i]; } V = N * 2; for(int i=0;i<N;i++){ for(int x=0;x<N;x++){ if(x != A[i]){ add_edge(i, N + x); } } } if(bipartite_matching() < N){ cout << -1 << endl; return 0; } for(int i=0;i<N;i++){ cout << match[i] - N << endl; } return 0; }