0-1 MST 【MST】1900

图片说明

Examples
input

output

input

3 0

output

题意

给你一个N个点的完全图，再指定哪些边是权值为1的边，没有指定的就是权值为0的边。问其最小生成树的权值是多少？

解法

令已经在MST上的点集合为A，还没有加入MST的为B。先任意加入一个点到A，然后将其它的全部放入到优先队列中{id,tim}，tim为一个点集合A的点边权为1的个数，每次从优先队列中取出一个边权1个数最少的，如果其边数 == ｜A｜，则只能用边权1的边相连接到MST，否则边数 < ｜A｜，则一定有边权为0可以与MST想连接。

对于维护优先队列，可以另外加一个cnt数组，记录边数的最新值，如果从优先队列取出的不是最新，则continue;

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------
int N,M;
vector<int> adj[maxn];
int cnt[maxn];
bool vis[maxn];
struct node{
    int u,tim;
    bool operator <(const node &o) const{
        return tim > o.tim;
    }
};
priority_queue<node> q;
void solve(){
    int sz = 1,ans = 0;
    for(int i = 2;i<=N;i++){
        q.push({i,0});
    }
    for(auto v:adj[1]){
        cnt[v]++;
        q.push({v,cnt[v]});
    }
    while(q.size()){
        node cur = q.top();q.pop();
        int u = cur.u,tim = cur.tim;
        if(tim != cnt[u]) continue; //不是最新值
        vis[u] = 1;
        if(tim >= sz) ans++;
        sz++;
        for(auto v:adj[u]){
            if(vis[v]) continue;
            cnt[v]++;
            q.push({v,cnt[v]});
        }
    }
    printf("%d\n",ans);
}
int main(){
    // debug_in;

    read(N,M);
    for(int i = 1;i<=M;i++){
        int x,y;read(x,y);
        adj[x].pb(y);
        adj[y].pb(x);
    }
    solve();


    return 0;
}