提出 #13256893

---

ソースコード 拡げる

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}

const int MAX_E = 1e5 + 1;

class KRUSKAL {

   public:
      int par[MAX_E];
      int UFTrank[MAX_E];
      struct edge { int u, v; double cost; };
      edge es[MAX_E * 2];
      int E, V;

      bool comp(const edge& e1, const edge& e2) {
         return e1.cost < e2.cost;
      }

      void init(int e, int v) {
         E = e;
         V = v;
         sort(es, es + E, [this] (edge& e1, edge& e2) { return  comp(e1, e2); } );
         for (int i = 0; i < V; i++) {
            par[i] = i;
            UFTrank[i] = 0;
         }
      }

      int find(int x) {
         if (par[x] == x) {
            return x;
         } else {
            return par[x] = find(par[x]);
         }
      }

      void unite(int x, int y) {
         x = find(x);
         y = find(y);
         if (x == y) return;

         if (UFTrank[x] < UFTrank[y]) {
            par[x] = y;
         } else {
            par[y] = x;
            if (UFTrank[x] == UFTrank[y]) UFTrank[x]++;
         }
      }

      bool same(int x, int y) {
         return find(x) == find(y);
      }

      double getmin() {
         int ans = 0;
         for (int i = 0; i < E; i++) {
            edge e = es[i];
            if (!same(e.u, e.v)) {
               unite(e.u, e.v);
               ans += e.cost;
            }
         }
         return ans;
      }
};
   
int N, M;
double x[35], y[35], c[35];
double X[10], Y[10], C[10];

double calc(int i, int j) {
   int c_i, c_j;
   double x_i, y_i, x_j, y_j;

   if (i < N) {
      c_i = c[i];
      x_i = x[i];
      y_i = y[i];
   } else {
      c_i = C[i - N];
      x_i = X[i - N];
      y_i = Y[i - N];
   }
   if (j < N) {
      c_j = c[j];
      x_j = x[j];
      y_j = y[j];
   } else {
      c_j = C[j - N];
      x_j = X[j - N];
      y_j = Y[j - N];
   }

   double res = 0.;
   
   res += pow(x_i - x_j, 2);
   res += pow(y_i - y_j, 2);
   res = sqrt(res);
   if (c_i != c_j) res *= 10.;
   return res;
}

int main() {
   cin >> N >> M;
   
   for (int i = 0; i < N; i++) {
      cin >> x[i] >> y[i] >> c[i];
   }
   for (int i = 0; i < M; i++) {
      cin >> X[i] >> Y[i] >> C[i];
   }
   
   double ans = -1.;
   for (int mask = 0; mask < (1<<M); mask++) {
      KRUSKAL mst;
      int V = N;
      for (int i = 0; i < M; i++) {
         if (((mask >> i) & 1)) V++;
      }
      int ed = 0;
      for (int i = 0; i < N + M; i++) {
         for (int j = i + 1; j < N + M; j++) {
            int i_small = i - N;
            int j_small = j - N;
            if (i_small >= 0 && !((mask >> i_small) & 1)) continue;
            if (j_small >= 0 && !((mask >> j_small) & 1)) continue;
            mst.es[ed].u = i;
            mst.es[ed].v = j;
            mst.es[ed].cost = calc(i, j);
            ed++;
         }
      }
      // cout << ed << " " << V << " " << mask << endl;
      mst.init(ed, V);
      double tmp = mst.getmin();
      if (ans < 0.) ans = tmp;
      else if (ans > tmp) ans = tmp;
   }
   cout << fixed << setprecision(7) << ans << endl;
   return 0;
}

提出情報

ジャッジ結果