#include <bits/stdc++.h>
using namespace std;
// Typedef
typedef long double ld;
typedef long long int int64;
typedef unsigned long long int uint64;
typedef std::pair<int, int> PII;
typedef std::pair<int64, int64> PLL;
typedef std::vector<int> VI;
typedef std::vector<long long> VLL;
// Define For-loop
#define FOR(i, j, k, in) for (int i = (j); i < (k) ; i += (in))
#define FORW(i, j, k, in) for (int i = (j); i <= (k); i += (in))
#define RFOR(i, j, k, in) for (int i = (j); i >= (k); i -= (in))
// Define Data structure func
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define sz(cont) int((cont).size())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
// Define number
#define IINF 0x3f3f3f3f
#define LLINF 1000111000111000111LL
#define PI 3.1415926535897932384626433832795
// Other
#define lend '\n'
#define hardio(name) freopen(name".inp","r",stdin), freopen(name".out","w",stdout);
void FastIO() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); cin.exceptions(cin.failbit); srand(time(NULL)); }
const int MOD = 1e9 + 7, MOD2 = 1e9 + 9;
// ======================================================================
struct Edge {
int a = 0, b = 0, w = IINF;
Edge() {};
Edge(int a_, int b_, int w_): a(a_), b(b_), w(w_) {};
};
struct Directed_MT {
int n;
vector<Edge> e;
int in[26], vis[26], par[26], id[26];
void init(int n_) { n = max(n_, 0); e.clear(); }
void addEdge(int a, int b, int w) {
e.pb(Edge(a, b, w));
}
int calc(int root) {
int ans = 0;
while (1) {
FOR(i, 0, n, 1) in[i] = IINF;
FOR(i, 0, sz(e), 1) {
int u = e[i].a, v = e[i].b;
if (e[i].w < in[v] && u != v) {
in[v] = e[i].w;
par[v] = u;
}
}
FOR(i, 0, n, 1) {
if (i == root) continue; // pass out the root
if (in[i] == IINF) return -1; // not enough edge
}
int cnt = 0;
memset(vis, -1, sizeof vis);
memset(id, -1, sizeof id);
in[root] = 0;
FOR(i, 0, n, 1) {
ans += in[i];
int t = i;
while (vis[t] != i && id[t] == -1 && t != root) {
vis[t] = i;
t = par[t];
}
if (t != root && id[t] == -1) {
for(int s = par[t]; s != t; s = par[s])
id[s] = cnt;
id[t] = cnt++;
}
}
if (cnt == 0) break;
FOR(i, 0, n, 1) if (id[i] == -1) id[i] = cnt++;
FOR(i, 0, sz(e), 1) {
int v = e[i].b;
e[i].b = id[e[i].b]; e[i].a = id[e[i].a];
if (e[i].a != e[i].b) {
e[i].w -= in[v];
}
}
n = cnt;
root = id[root];
}
return ans;
}
} T;
int n, k, a[36] = {};
int c[36][36] = {};
int calc() {
T.init(n + 1);
FORW(i, 1, n, 1) {
if (a[i] == 1) T.addEdge(n, i - 1, 0);
else {
FORW(j, 1, n, 1)
if (i != j) T.addEdge(j - 1, i - 1, c[i][j]);
}
}
return T.calc(n);
}
int main(int argc, char* argv[]) {
FastIO();
cin >> n >> k;
FORW(i, 1, n, 1) FORW(j, 1, n, 1) cin >> c[i][j];
FORW(i, 1, n - k, 1) a[i] = 0; // bottle we will get rid
FORW(i, n - k + 1, n, 1) a[i] = 1; // bottle we will keep
int ans = IINF;
do {
ans = min(ans, calc());
} while (next_permutation(a + 1, a + 1 + n));
cout << ans << endl;
return 0; }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
216 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
320 KB |
Output is correct |
| 5 |
Correct |
5 ms |
324 KB |
Output is correct |
| 6 |
Correct |
5 ms |
204 KB |
Output is correct |
| 7 |
Correct |
18 ms |
328 KB |
Output is correct |
| 8 |
Correct |
37 ms |
308 KB |
Output is correct |
| 9 |
Correct |
10 ms |
332 KB |
Output is correct |
| 10 |
Correct |
171 ms |
204 KB |
Output is correct |
