結果
| 問題 |
No.2263 Perms
|
| コンテスト | |
| ユーザー |
 hari64
|
| 提出日時 | 2023-04-07 22:12:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,126 bytes |
| コンパイル時間 | 2,485 ms |
| コンパイル使用メモリ | 212,688 KB |
| 最終ジャッジ日時 | 2025-02-12 01:34:57 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 WA * 2 RE * 7 |
ソースコード
#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>(M));
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);
for (auto& e : g.edges()) {
debug(e.cap, e.flow, e.from, e.to);
}
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;
}