#857477 (C++17) No.2263 Perms

提出ソース

結果

問題	No.2263 Perms
ユーザー	hari64
提出日時	2023-04-07 22:23:21
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	7,032 bytes
コンパイル時間	2,671 ms
コンパイル使用メモリ	218,136 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-10-02 19:51:17
合計ジャッジ時間	4,445 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	WA	-
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	11 ms 6,816 KB
testcase_07	AC	11 ms 6,816 KB
testcase_08	AC	9 ms 6,816 KB
testcase_09	AC	10 ms 6,816 KB
testcase_10	WA	-
testcase_11	AC	12 ms 6,820 KB
testcase_12	AC	11 ms 6,820 KB
testcase_13	AC	11 ms 6,816 KB
testcase_14	AC	11 ms 6,820 KB
testcase_15	AC	10 ms 6,816 KB
testcase_16	AC	2 ms 6,816 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,820 KB
testcase_19	AC	3 ms 6,816 KB
testcase_20	AC	9 ms 6,820 KB
testcase_21	AC	9 ms 6,816 KB
testcase_22	AC	8 ms 6,820 KB
testcase_23	AC	4 ms 6,816 KB
testcase_24	AC	3 ms 6,820 KB
testcase_25	AC	9 ms 6,820 KB
testcase_26	AC	10 ms 6,820 KB
testcase_27	AC	5 ms 6,816 KB
testcase_28	AC	3 ms 6,816 KB
testcase_29	AC	3 ms 6,816 KB
testcase_30	AC	2 ms 6,820 KB
testcase_31	AC	2 ms 6,816 KB
testcase_32	AC	3 ms 6,816 KB
testcase_33	AC	2 ms 6,816 KB
testcase_34	AC	2 ms 6,820 KB
testcase_35	AC	2 ms 6,816 KB
testcase_36	AC	3 ms 6,820 KB
testcase_37	AC	2 ms 6,820 KB
testcase_38	AC	9 ms 6,820 KB
testcase_39	AC	2 ms 6,816 KB
testcase_40	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifndef hari64
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#define debug(...)
#else
#include "util/viewer.hpp"
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif
using namespace std;
constexpr int INF = 1001001001;
constexpr long long INFll = 1001001001001001001;
template <class T>
bool chmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}

// clang-format off
template<class T>
struct simple_queue{vector<T>payload;int pos=0;void reserve(int n){payload.reserve(n);}int size()const{return int(payload.size())-pos;}bool empty()const{return pos==int(payload.size());}void push(const T&t){payload.push_back(t);}T&front(){return payload[pos];}void clear(){payload.clear();pos=0;}void pop(){pos++;}};
template<class Cap=long long>
struct mf_graph{
    mf_graph():_n(0){};explicit mf_graph(int n):_n(n),g(n){};struct edge{int from,to;Cap cap,flow;};
    // fromからtoへ最大容量cap、流量 0 の辺を追加し、何番目に追加された辺かを返す
    int add_edge(int from,int to,Cap cap){assert(0<=from&&from<_n);assert(0<=to&&to<_n);assert(0<=cap);int m=int(pos.size());pos.push_back({from,int(g[from].size())});int from_id=int(g[from].size());int to_id=int(g[to].size());if(from==to)to_id++;g[from].push_back(_edge{to,to_id,cap});g[to].push_back(_edge{from,from_id,0});return m;}
    // 今の内部の辺の状態を返す 辺の順番はadd_edgeで追加された順番と同一
    edge get_edge(int i){assert(0<=i&&i<int(pos.size()));auto _e=g[pos[i].first][pos[i].second];auto _re=g[_e.to][_e.rev];return edge{pos[i].first,_e.to,_e.cap+_re.cap,_re.cap};}
    // 今の内部の辺の状態を返す 辺の順番はadd_edgeで追加された順番と同一
    vector<edge>edges(){vector<edge>result;for(int i=0;i<int(pos.size());i++){result.push_back(get_edge(i));}return result;}
    // i 番目に追加された辺の容量、流量をnew_cap, new_flowに変更する 他の辺の容量、流量は変更しない
    void change_edge(int i,Cap new_cap,Cap new_flow){int m=int(pos.size());assert(0<=i&&i<m);assert(0<=new_flow&&new_flow<=new_cap);auto&_e=g[pos[i].first][pos[i].second];auto&_re=g[_e.to][_e.rev];_e.cap=new_cap-new_flow;_re.cap=new_flow;}
    // 頂点 s から t へ流せる限り流し、流せた量を返す 複数回呼ぶことも可能
    Cap flow(int s,int t){return flow(s,t,numeric_limits<Cap>::max());}
    // 頂点 s から t へ流量 flow_limit に達するまで流せる限り流し、 流せた量を返す  複数回呼ぶことも可能
    Cap flow(int s,int t,Cap flow_limit){assert(0<=s&&s<_n);assert(0<=t&&t<_n);assert(s!=t);vector<int>level(_n),iter(_n);simple_queue<int>que;
        auto bfs=[&](){fill(level.begin(),level.end(),-1);level[s]=0;que.clear();que.push(s);while(!que.empty()){int v=que.front();que.pop();for(auto e:g[v]){if(e.cap==0||level[e.to]>=0)continue;level[e.to]=level[v]+1;if(e.to==t)return;que.push(e.to);}}};
        auto dfs=[&](auto self,int v,Cap up){if(v==s)return up;Cap res=0;int level_v=level[v];for(int&i=iter[v];i<int(g[v].size());i++){_edge&e=g[v][i];if(level_v<=level[e.to]||g[e.to][e.rev].cap==0)continue;Cap d=self(self,e.to,min(up-res,g[e.to][e.rev].cap));if(d<=0)continue;g[v][i].cap+=d;g[e.to][e.rev].cap-=d;res+=d;if(res==up)return res;}level[v]=_n;return res;};
        Cap flow=0;while(flow<flow_limit){bfs();if(level[t]==-1)break;fill(iter.begin(),iter.end(),0);Cap f=dfs(dfs,t,flow_limit-flow);if(!f)break;flow+=f;}return flow;}
    // 長さ n のvectorを返す i 番目の要素には、頂点 s から i へ残余グラフで到達可能なとき、またその時のみ true を返す
    // flow(s,t)をflow_limitなしでちょうど一回呼んだ後に呼ぶと、返り値は s,t 間のmincutに対応します
    vector<bool>min_cut(int s){vector<bool>visited(_n);simple_queue<int>que;que.push(s);while(!que.empty()){int p=que.front();que.pop();visited[p]=true;for(auto e:g[p]){if(e.cap&&!visited[e.to]){visited[e.to]=true;que.push(e.to);}}}return visited;}
    // debug用
    string state(){string ret("\n");for(auto&e:edges())ret+="[from,to/cap,flow]:"+to_string(e.from)+","+to_string(e.to)+"/"+to_string(e.cap)+","+to_string(e.flow)+"\n";return ret;}
   private:
    int _n;struct _edge{int to,rev;Cap cap;};vector<pair<int,int>>pos;vector<vector<_edge>>g;
};
// 最小流量制限付き最大流
// ref: https://snuke.hatenablog.com/entry/2016/07/10/043918
//  s        t  S→T,s→T,S→t,s→tと流す
//   ↘     ↗   先に最小流量制限分だけ流しておくというのが基本的な考え方
//    u -> v    u → v は一つを取り出しているだけなので、逆向きの辺も存在
//     ↘↗    
//  S -   -> T  蟻本などではS→s,t→Tに∞の容量の辺を張っている
template<class Cap>
struct mf_graph_lb{
    mf_graph_lb(int n):g(n+2),S(n),T(n+1),sum_lb(0){}
    // fromからtoへ最小流量制限low、 最大容量high、流量 0 の辺を追加する
    void add_edge(int from,int to,Cap low,Cap high){assert(from!=to&&high>=low);g.add_edge(from,to,high-low);if(low!=0){g.add_edge(S,to,low);g.add_edge(from,T,low);sum_lb+=low;}}
    // 頂点 s から t へ流せる限り流し、流せた量を返す 制約を満たせない場合 -1
    Cap flow(int s,int t){assert(s!=t);Cap a=g.flow(S,T);Cap b=g.flow(s,T);Cap c=g.flow(S,t);Cap d=g.flow(s,t);debug(make_tuple(a,b,c,d));return(a+c==sum_lb&&a+b==sum_lb)?b+d:-1;}
   private:
    mf_graph<Cap>g;int S,T;Cap sum_lb;
};
// clang-format on

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;
    vector<vector<int>> As(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> As[i][j];
        }
    }

    vector<vector<int>> ans;
    for (int _ = 0; _ < M; _++) {
        mf_graph g(2 * N + 2);
        int s = 2 * N;
        int t = 2 * N + 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g.add_edge(i, N + j, As[i][j]);
            }
        }
        for (int i = 0; i < N; i++) {
            g.add_edge(s, i, 1);
        }
        for (int i = 0; i < N; i++) {
            g.add_edge(N + i, t, 1);
        }
        auto res = g.flow(s, t, N);
        debug(res);
        if (res != N) {
            cout << -1 << endl;
            return 0;
        }
        ans.push_back({});
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                auto e = g.get_edge(i * N + j);
                if (e.flow == 1) {
                    ans.back().push_back(j + 1);
                    As[i][j]--;
                }
            }
        }
        assert(int(ans.back().size()) == N);
    }

    for (auto& elems : ans) {
        for (auto& elem : elems) cout << elem << " ";
        cout << endl;
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード