글 읽기 - 4343 저만 잘못 이해하고있는건가요? [위성으로 처리해줄 수 있는 간선 수]

mym0404 3년 전 0

위성이 S개 있는데, 인터넷에서 찾아본 풀이법들은 S - 1 개의 간선을 MST에서 제거해서 남은 MST에서 가장 큰 간선의 가중치를 답이라고 하는데,

예를들어 위성이 3개있고 기지가 4개있을 때,

input이 다음과 같다고 하겠습니다.

3 4

0 0

100 0

101 0

201 0

이라고 한다면, MST는 1,2,3,4번째 기지를 순서대로 이은 1-2, 2-3, 3-4 가 될 것입니다.

여기서 위성 1-2와 3-4의 거리가 각각 100이기 때문에, 그냥 S - 1 개(2개)의 간선을 지워버린다면 정답은 1.00 이 됩니다.

그런데, 위성 3개로는 1,2,3,4에 모두 위성을 설치할 수가 없어서 정답은 100.00 이 되어야 하지 않을까요?

1.00 이 나오는 답이 정해가 되고 정답이 통과되어서 문제를 잘못이해한 부분이 있는지 질문드립니다.

소스코드는 일부로 assert를 찍어놓은 소스코드이고 RTE가 아니고 WA가 나옵니다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define endl "\n"
#define pb push_back
#define all(X) begin((X)), end((X))
#define sz(X) (int)(X).size()
#define fi first
#define se second
#define fv(X) for(auto&_:(X))cin>>_
#define fv2(X) for(auto&_1:(X))for(auto&_2:_1)cin>>_2
#ifdef LOCAL
string to_string(const string &x) { return x; }
string to_string(bool x) { return x ? "true" : "false"; }
template<typename Head, typename Tail>
string to_string(const pair<Head, Tail> &x) { return "(" + to_string(x.fi) + ", " + to_string(x.se) + ")"; }
template<class T>
string to_string(T x) {
   string ret = "[";
   for (const auto &i: x)
      ret += to_string(i) + ", ";
   if (sz(ret) > 1)
      ret = ret.substr(0, sz(ret) - 2);
   return ret += "]";
}
string to_string(const char *x) { return string(x); }
string to_string() { return ""; }
template<typename Head, typename... Tail>
string to_string(Head H, Tail... T) { return to_string(H) + ", " + to_string(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: " << to_string(__VA_ARGS__) << endl
#else
#define debug(...)
#endif
class DSU {
public:
   vector<int> p;
   bool upside;
   DSU(int n, bool up = false) {
      p.resize(n);
      for (int i = 0; i < n; i++)
         p[i] = i;
      upside = up;
   }
   int gp(int n) {
      if (p[n] == n)
         return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b) {
      a = gp(a);
      b = gp(b);
      if (a < b && !upside || a > b && upside)
         p[b] = a;
      else
         p[a] = b;
   }
   bool is_merged(int a, int b) {
      return gp(a) == gp(b);
   }
};
struct Edge {
   int from, to;
   ll cost;

   Edge(int from, int to, ll cost) : from(from), to(to), cost(cost) {}

   bool operator<(const Edge &e) const {
      return cost < e.cost;
   }
};
vector<Edge> edges;
ll len(pl a, pl b) {
   return (a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se);
}

void solve() {
   edges.clear();
   int S, P;
   cin >> S >> P;
   vector<pl> outposts(P);
   for (int i = 0; i < P; i++)
      cin >> outposts[i].fi >> outposts[i].se;
   for (int i = 0; i < P; i++)
      for (int j = i + 1; j < P; j++)
         edges.pb(Edge(i, j, len(outposts[i], outposts[j])));
   sort(all(edges));
   DSU dsu(P);
   vector<Edge> mst;
   for (Edge e: edges) {
      if (!dsu.is_merged(e.from, e.to)) {
         debug(e.from, e.to, e.cost);
         dsu.merge(e.from, e.to);
         mst.pb(Edge(e.from, e.to, e.cost));
      }
   }
   reverse(all(mst));
   vi set_sat(P, false);

   ll ret = -1;
   for (auto e: mst) {
      if (set_sat[e.from] && set_sat[e.to]) {
         continue;
      }
      if (set_sat[e.from] || set_sat[e.to]) {
         if (S < 1) {
            ret = e.cost;
            break;
         }
         S--;
         set_sat[e.from] = true;
         set_sat[e.to] = true;
         continue;
      }
      if (!set_sat[e.from] && !set_sat[e.to]) {
         if (S < 2) {
            ret = e.cost;
            break;
         }
         S -= 2;
         set_sat[e.from] = true;
         set_sat[e.to] = true;
         continue;
      }
   }
   assert(ret != -1);
   cout.precision(2);
   double ans = sqrt(ret);
   cout << fixed << ans << endl;
}

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int TT;
   cin >> TT;
   while (TT--)
      solve();
   return 0;
}

palilo 3년 전 1

1,2,4에 위성을 설치해주면 1,2,4끼리는 전부 연결됐고 얘들끼리의 통신 비용은 0입니다.

이제 3 하나만 이어주면 되는데

1-3 사이를 이어줄 경우 비용은 101,

2-3 사이를 이어줄 경우 비용은 1,

3-4 사이를 이어줄 경우 비용은 100 입니다.

저기서 최솟값은 1이니까, 비용을 1만 내면 1,2,3,4가 전부 연결되겠네요

mym0404 3년 전 0

감사합니다

MST를 먼저 만들고 그걸 갖고 뭘 하는 문제가 아니였군요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4343 저만 잘못 이해하고있는건가요? [위성으로 처리해줄 수 있는 간선 수]

mym0404 3년 전 0

palilo 3년 전 1

mym0404 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말