oj.uz

답안 #447357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447357 2021-07-26T07:03:14 Z XBoRickie Kronican (COCI16_kronican) C++11
100 / 100
 171 ms 332 KB 
#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; }

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 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