結果
問題 | No.2573 moving up |
ユーザー |
![]() |
提出日時 | 2023-12-15 15:58:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,396 ms / 2,000 ms |
コード長 | 3,584 bytes |
コンパイル時間 | 1,785 ms |
コンパイル使用メモリ | 126,068 KB |
実行使用メモリ | 10,304 KB |
最終ジャッジ日時 | 2024-09-27 06:28:14 |
合計ジャッジ時間 | 18,673 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;using ll = long long;#include<queue>#include<limits>template< typename flow_t, typename cost_t >struct PrimalDual {const cost_t INF;struct edge {int to;flow_t cap;cost_t cost;int rev;bool isrev;};vector< vector< edge > > graph;vector< cost_t > potential, min_cost;vector< int > prevv, preve;PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}void add_edge(int from, int to, flow_t cap, cost_t cost) {graph[from].emplace_back((edge) {to, cap, cost, (int) graph[to].size(), false});graph[to].emplace_back((edge) {from, 0, -cost, (int) graph[from].size() - 1, true});}cost_t min_cost_flow(int s, int t, flow_t f) {int V = (int) graph.size();cost_t ret = 0;using Pi = pair< cost_t, int >;priority_queue< Pi, vector< Pi >, greater< Pi > > que;potential.assign(V, 0);preve.assign(V, -1);prevv.assign(V, -1);while(f > 0) {min_cost.assign(V, INF);que.emplace(0, s);min_cost[s] = 0;while(!que.empty()) {Pi p = que.top();que.pop();if(min_cost[p.second] < p.first) continue;for(int i = 0; i < graph[p.second].size(); i++) {edge &e = graph[p.second][i];cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to];if(e.cap > 0 && min_cost[e.to] > nextCost) {min_cost[e.to] = nextCost;prevv[e.to] = p.second, preve[e.to] = i;que.emplace(min_cost[e.to], e.to);}}}if(min_cost[t] == INF) return -1;for(int v = 0; v < V; v++) potential[v] += min_cost[v];flow_t addflow = f;for(int v = t; v != s; v = prevv[v]) {addflow = min(addflow, graph[prevv[v]][preve[v]].cap);}f -= addflow;ret += addflow * potential[t];for(int v = t; v != s; v = prevv[v]) {edge &e = graph[prevv[v]][preve[v]];e.cap -= addflow;graph[v][e.rev].cap += addflow;}}return ret;}void output() {for(int i = 0; i < graph.size(); i++) {for(auto &e : graph[i]) {if(e.isrev) continue;auto &rev_e = graph[e.to][e.rev];cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl;}}}};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int h,w;cin>>h>>w;int m = h + w + 1;PrimalDual<ll,ll> g(2 + w + w);int st = w + w;int tt = st + 1;int dx[] = {-1,-1,0,0,1,1};int dy[] = {-1,0,-1,1,0,1};for(int i = 0;i<w;i++){g.add_edge(st,i,1,0);g.add_edge(i+w,tt,1,0);vector<vector<int>> vis(m,vector<int>(m,1e9));int x,y;cin>>x>>y;x--;y--;vis[x][y] = 0;vector<pair<int,int>> que;que.push_back(make_pair(x,y));for(int j = 0;j<que.size();j++){int ni = que[j].first;int nj = que[j].second;for(int k = 0;k<6;k++){int nni = ni + dx[k];int nnj = nj + dy[k];if(nni<0||nnj<0||nnj>=w+nni||nni>=m||nnj>=m) continue;if(vis[nni][nnj]<=vis[ni][nj]+1) continue;vis[nni][nnj] = vis[ni][nj] + 1;que.push_back(make_pair(nni,nnj));}}for(int j = 0;j<w;j++) g.add_edge(i,j+w,1,vis[0][j]);}cout<<g.min_cost_flow(st,tt,w)<<endl;}