library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aoj0274.test.cpp
- View this file on GitHub
- Last update: 2021-06-21 15:24:20+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0274
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0274"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;
template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
#include "../util/makev.cpp"
#include "../flow/primaldual.cpp"
void solve(int d, int k, int l){
vector<vector<int>> v(d, vector<int>(k, 0));
for (int i = 0; i < d; ++i) {
for (int j = 0; j < k; ++j) {
cin >> v[i][j];
}
}
auto dp = make_v(d+1, l+1, 1 << (2*k), INF<int>);
dp[0][0][0] = 0;
for (int i = 0; i < d; ++i) {
for (int j = 0; j <= l; ++j) {
for (int m = 0; m < 1 << (2*k); ++m) {
chmin(dp[i+1][0][m], dp[i][j][m]);
if(j == l || dp[i][j][m] == INF<int>) continue;
for (int n = 0; n < k; ++n) {
if(((m >> 2*n)&3) == 2) continue;
chmin(dp[i][j+1][m+(1 << 2*n)], dp[i][j][m]+v[i][n]);
}
}
}
}
int m, n, p;
cin >> m >> n >> p;
auto R = make_v(m, k, 0);
auto T = make_v(p+1, k, 0);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < k; ++j) {
cin >> R[i][j];
}
}
for (int i = 0; i < p; ++i) {
for (int j = 0; j < k; ++j) {
cin >> T[i][j];
}
}
p++;
PrimalDual<int, int> G(m+p+2);
for (int i = 0; i < m; ++i) {
G.add_edge(0, i+2, 1, 0);
}
for (int i = 0; i < p; ++i) {
G.add_edge(m+2+i, 1, (i == p-1 ? n : 1), 0);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < p; ++j) {
int S = 0;
for (int o = 0; o < k; ++o) {
if(R[i][o] < T[j][o]) {
S = -1;
break;
}
S |= (1 << 2*o)*(R[i][o]-T[j][o]);
}
if(S >= 0 && dp.back()[0][S] < INF<int>){
G.add_edge(i+2, m+2+j, 1, dp.back()[0][S]);
}
}
}
int ok = 0;
auto res = G.flow(0, 1, n, ok);
if(!ok) puts("-1");
else cout << res << "\n";
}
int main() {
int d, k, l;
while(cin >> d >> k >> l, d){
solve(d, k, l);
}
return 0;
}#line 1 "test/aoj0274.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0274"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;
template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
#line 1 "util/makev.cpp"
template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }
template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }
template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }
/**
* @brief make_v, chmin, chmax
* @docs _md/makev.md
*/
#line 21 "test/aoj0274.test.cpp"
#line 1 "flow/primaldual.cpp"
template<typename F, typename C>
struct PrimalDual {
struct edge {
int to; F cap; C cost; int rev;
edge() = default;
edge(int to, F cap, C cost, int rev):to(to), cap(cap), cost(cost), rev(rev) {};
};
vector<vector<edge>> G;
vector<C> potential, min_cost;
vector<int> prevv, preve;
explicit PrimalDual(int n) : G(n), potential(n), min_cost(n), prevv(n), preve(n) {}
void add_edge(int u, int v, F cap, C cost){
G[u].emplace_back(v, cap, cost, G[v].size());
G[v].emplace_back(u, 0, -cost, G[u].size()-1);
}
struct P{
C first; int second;
P(C first,int second):first(first),second(second){}
bool operator<(const P&a) const{return a.first<first;}
};
void dijkstra(int s){
priority_queue<P> Q;
fill(min_cost.begin(),min_cost.end(), INF<C>);
min_cost[s] = 0;
Q.emplace(0, s);
while(!Q.empty()){
P p = Q.top(); Q.pop();
int v = p.second;
if(min_cost[v] < p.first) continue;
for(int i = 0; i < G[v].size(); ++i){
edge &e=G[v][i];
if(e.cap==0) continue;
if(min_cost[v]+e.cost+potential[v]-potential[e.to] < min_cost[e.to]){
min_cost[e.to] = min_cost[v]+e.cost+potential[v]-potential[e.to];
prevv[e.to] = v;
preve[e.to] = i;
Q.emplace(min_cost[e.to], e.to);
}
}
}
}
C flow(int s, int t, F fl, int &ok){
C res = 0;
fill(potential.begin(),potential.end(), 0);
while(fl > 0){
dijkstra(s);
if(min_cost[t] == INF<C>){
ok = 0;
return res;
}
for (int i = 0; i < potential.size(); ++i) {
if(min_cost[i] < INF<C>) potential[i] += min_cost[i];
}
F d = fl;
for(int v = t; v != s; v = prevv[v]){
d = min(d, G[prevv[v]][preve[v]].cap);
}
fl -= d;
res += potential[t]*d;
for(int v = t; v != s; v = prevv[v]){
G[prevv[v]][preve[v]].cap -= d;
G[v][G[prevv[v]][preve[v]].rev].cap += d;
}
}
ok = 1;
return res;
}
};
/**
* @brief 最小費用流(primal-dual)
* @docs _md/primaldual.md
*/
#line 23 "test/aoj0274.test.cpp"
void solve(int d, int k, int l){
vector<vector<int>> v(d, vector<int>(k, 0));
for (int i = 0; i < d; ++i) {
for (int j = 0; j < k; ++j) {
cin >> v[i][j];
}
}
auto dp = make_v(d+1, l+1, 1 << (2*k), INF<int>);
dp[0][0][0] = 0;
for (int i = 0; i < d; ++i) {
for (int j = 0; j <= l; ++j) {
for (int m = 0; m < 1 << (2*k); ++m) {
chmin(dp[i+1][0][m], dp[i][j][m]);
if(j == l || dp[i][j][m] == INF<int>) continue;
for (int n = 0; n < k; ++n) {
if(((m >> 2*n)&3) == 2) continue;
chmin(dp[i][j+1][m+(1 << 2*n)], dp[i][j][m]+v[i][n]);
}
}
}
}
int m, n, p;
cin >> m >> n >> p;
auto R = make_v(m, k, 0);
auto T = make_v(p+1, k, 0);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < k; ++j) {
cin >> R[i][j];
}
}
for (int i = 0; i < p; ++i) {
for (int j = 0; j < k; ++j) {
cin >> T[i][j];
}
}
p++;
PrimalDual<int, int> G(m+p+2);
for (int i = 0; i < m; ++i) {
G.add_edge(0, i+2, 1, 0);
}
for (int i = 0; i < p; ++i) {
G.add_edge(m+2+i, 1, (i == p-1 ? n : 1), 0);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < p; ++j) {
int S = 0;
for (int o = 0; o < k; ++o) {
if(R[i][o] < T[j][o]) {
S = -1;
break;
}
S |= (1 << 2*o)*(R[i][o]-T[j][o]);
}
if(S >= 0 && dp.back()[0][S] < INF<int>){
G.add_edge(i+2, m+2+j, 1, dp.back()[0][S]);
}
}
}
int ok = 0;
auto res = G.flow(0, 1, n, ok);
if(!ok) puts("-1");
else cout << res << "\n";
}
int main() {
int d, k, l;
while(cin >> d >> k >> l, d){
solve(d, k, l);
}
return 0;
}