結果

問題 No.241 出席番号(1)
ユーザー dnish
提出日時 2018-03-20 11:30:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,058 bytes
コンパイル時間 665 ms
コンパイル使用メモリ 81,528 KB
最終ジャッジ日時 2024-11-14 20:23:36
合計ジャッジ時間 1,077 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In member function 'V MaxFlow<V>::maxflow(int, int)':
main.cpp:53:66: error: 'numeric_limits' was not declared in this scope
   53 |             REP(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;
      |                                                                  ^~~~~~~~~~~~~~
main.cpp:53:82: error: expected primary-expression before '>' token
   53 |             REP(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;
      |                                                                                  ^
main.cpp:53:88: error: no matching function for call to 'max()'
   53 |             REP(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;
      |                                                                                   ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/algorithm:60,
                 from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
main.cpp:53:88: note:   candidate expects 2 arguments, 0 provided
   53 |             REP(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;
      |                                                                                   ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/home/linuxbrew/.linuxb

ソースコード

diff # 

#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;
}
0