답안 #447359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447359 2021-07-26T07:06:45 Z XBoRickie Kronican (COCI16_kronican) C++11
100 / 100
84 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, m;
    Edge e[406];

    int in[26], vis[26], par[26], id[26];

    void init(int n_) { n = max(n_, 0); m = 0; }
    void addEdge(int a, int b, int w) {
        e[m++] = Edge(a, b, w);
    }

    int calc(int root) {
        int ans = 0;
        while (1) {
            FOR(i, 0, n, 1) in[i] = IINF;
            FOR(i, 0, m, 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, m, 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();

    scanf("%d%d", &n, &k);
    FORW(i, 1, n, 1) FORW(j, 1, n, 1) scanf("%d", &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));
    printf("%d", ans);

    return 0; }

Compilation message

kronican.cpp: In function 'int main(int, char**)':
kronican.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
kronican.cpp:121:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     FORW(i, 1, n, 1) FORW(j, 1, n, 1) scanf("%d", &c[i][j]);
      |                                       ~~~~~^~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Correct 8 ms 332 KB Output is correct
8 Correct 16 ms 324 KB Output is correct
9 Correct 6 ms 204 KB Output is correct
10 Correct 84 ms 204 KB Output is correct