#245609 (C++17(gcc12)) No.241 出席番号(1)

• 問題: No.241 出席番号(1)
• ユーザー: dnish
• 提出日時: 2018-03-20 11:30:28
• 言語: C++17(gcc12) (gcc 12.4.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,058 bytes
• コンパイル時間: 1,207 ms
• コンパイル使用メモリ: 116,968 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2026-03-08 19:04:37
• 合計ジャッジ時間: 2,377 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 29

ソースコード

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf = 1e9+7;

template<class V> struct MaxFlow {
    struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} };
    int MV; vector< vector<edge> > E; vector<int> itr, lev;
    MaxFlow(int n) { init(n); } MaxFlow() { }
    void init(int n) { MV = n; itr = vector<int>(MV), lev = vector<int>(MV); E = vector< vector<edge> >(MV); }
    void add_edge(int x, int y, V cap, bool undir = false) {
        E[x].push_back(edge(y, (int)E[y].size(), cap));
        E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0));
    }
    void bfs(int cur) {
        REP(i, 0, MV) lev[i] = -1; queue<int> q; lev[cur] = 0; q.push(cur);
        while (q.size()) {
            int v = q.front(); q.pop();
            for (auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to);
        }
    }
    V dfs(int from, int to, V cf) {
        if (from == to) return cf;
        for (; itr[from]<E[from].size(); itr[from]++) {
            edge* e = &E[from][itr[from]]; if (e->cap>0 && lev[from]<lev[e->to]) {
                V f = dfs(e->to, to, min(cf, e->cap));
                if (f>0) { e->cap -= f; E[e->to][e->reve].cap += f; return f; }
            }
        } return 0;
    }
    V maxflow(int from, int to) {
        V fl = 0, tf;
        while (1) {
            bfs(from); if (lev[to]<0) return fl;
            REP(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;
        }
    }
};


// 二部最大マッチング
struct BipartiteMatching {
    int N, M; MaxFlow<int> mf;
    //コンストラクタ(引数は各集合のノード数)
    BipartiteMatching(int n, int m) : N(n), M(m) { mf.init(n + m + 2); }
    //辺を作成してグラフをつくる（引数は各集合内で一意なノード識別番号）
    void add_edge(int a, int b) { mf.add_edge(a, N + b, 1); }
    //最大マッチング数を返す
    int match() { REP(a, 0, N) mf.add_edge(N + M, a, 1); REP(b, 0, M) mf.add_edge(N + b, N + M + 1, 1);
        return mf.maxflow(N + M, N + M + 1); }
    // マッチング相手を返す(無いなら-1)
    int whois(int a) { for (auto e : mf.E[a]) if (e.cap == 0) return e.to - N; return -1; }
};

int N;
int A[55];
int ans[55];
int main(){
    cin >> N;
    REP(y, 0, N) cin >> A[y];

    BipartiteMatching bm(N, N);//生徒, 数字
    REP(i, 0, N) REP(j, 0, N) {
        if (A[i]!=j) {
            bm.add_edge(i, j);
        }
    }
    int mxmatch = bm.match();
    if(mxmatch!=N) p(-1);
    else{
        REP(i,0,N){
            p(bm.whois(i));
        }
    }

    return 0;
}