BZOJ3714 PA2014 Kuglarz 最小生成树

题目传送门

题意：有$N$个盒子，每个盒子中有$0$或$1$个球。现在你可以花费$c_{i,j}$的代价获得$i$到$j$的盒子中球的总数的奇偶性，求最少需要多少代价才能知道哪些盒子中有球。$N \leq 2000 , 1 \leq c \leq 10^9$

初赛凉了，乖乖回来更以前没写的blog qwq

设$s_i$为盒子中球数的前缀和$(s_0 = 0)$，那么我们花费$c_{i,j}$就是得到$s_{i-1}$与$s_j$的关系，而我们知道$s_i,s_j$与$s_j,s_k$的关系之后，就能知道$s_i$与$s_k$的关系。我们可以考虑使用并查集维护这个关系，然后：咦这不就是$Kruskal$吗？然后跑遍最小生成树就出来了

反正我是有生之年不会想到这道题和最小生成树相关的了QuQ

还有Prim用堆优化真心卵用没有

 #include<bits/stdc++.h>
 #define MAXN 2001
 using namespace std;
 inline int read(){
     ;
     ;
     char c;
     fread(&c ,  , stdin);
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         fread(&c ,  , stdin);
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         fread(&c ,  , stdin);
     }
     return f ? -a : a;
 }
 int Edge[MAXN][MAXN];
 bool vis[MAXN];
 priority_queue < pair < int , int > > q;
 int main(){
     ;
     int N = read();
      ; i <= N ; i++)
         for(int j = i ; j <= N ; j++)
             Edge[i - ][j] = Edge[j][i - ] = read();
     q.push(make_pair( , ));
     while(!q.empty()){
         int t = q.top().second;
         if(vis[t]){
             q.pop();
             continue;
         }
         ans += -q.top().first;
         vis[t] = ;
         q.pop();
          ; i <= N ; i++)
             if(!vis[i])
                 q.push(make_pair(-Edge[t][i] , i));
     }
     cout << ans;
     ;
 }

巴特西

BZOJ3714 PA2014 Kuglarz 最小生成树

最新文章

热门文章