結果
問題 | No.241 出席番号(1) |
ユーザー | koyumeishi |
提出日時 | 2015-07-10 22:44:24 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,782 bytes |
コンパイル時間 | 806 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 21:21:27 |
合計ジャッジ時間 | 2,210 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <iostream>#include <vector>#include <cstdio>#include <sstream>#include <map>#include <string>#include <algorithm>#include <queue>#include <cmath>#include <set>using namespace std;struct edge{int to;int cap;int rev;bool is_rev;};int Ford_Fulkerson_dfs(vector<vector<edge> > &G, int pos, int flow, vector<bool> &used, int t){if(pos == t){return flow;}else{used[pos] = true;for(int i=0; i<G[pos].size(); i++){if(!used[G[pos][i].to] && G[pos][i].cap >0){int myflow = Ford_Fulkerson_dfs(G, G[pos][i].to, min(flow, G[pos][i].cap), used, t);if(myflow > 0){G[pos][i].cap -= myflow;G[ G[pos][i].to ][ G[pos][i].rev ].cap += myflow;return myflow;}}}return 0;}}int Ford_Fulkerson(vector<vector<edge> > &G, int s, int t){const int INF = 100000000;int flow=0;for(;;){vector<bool> used(G.size(), false);int f = Ford_Fulkerson_dfs(G, s, INF, used, t);if(f==0) break;else flow += f;}return flow;}void add_edge(vector<vector<edge> > &G, int from, int to, int cap){G[from].push_back( (edge){to, cap, (int)G[to].size(), false} );G[to].push_back( (edge){from, 0, (int)G[from].size()-1, true} );}int main(){int N;cin >> N;vector<int> A(N);for(int i=0; i<N; i++){cin >> A[i];}vector<vector<edge>> G(2*N+2);int s = 2*N;int t = 2*N+1;for(int i=0; i<N; i++){add_edge(G, s, i, 1);add_edge(G, N+i, t, 1);for(int j=0; j<N; j++){if(j == A[i]) continue;add_edge(G, i, N+j, 1);}}int f = Ford_Fulkerson(G, s,t);if(f != N){cout << -1 << endl;return 0;}for(int i=0; i<N; i++){for(int j=0; j<G[i].size(); j++){if(G[i][j].cap == 0 && G[i][j].is_rev == false){cout << G[i][j].to-N << endl;}}}return 0;}