CF1687B Railway System 题解

题目传送门
可能更好的阅读体验

题目大意

交互题，给定 n,m，代表有一张 n 个点 m 条边的带权无向图。
每次询问，可以删除一些边（询问独立），得删掉这些边的最大生成森林。
现在 2m 次询问内求整张图片的最小生成森林。（最后输出答案不算询问）

生成森林的定义是选择图中的一些边，使得图的连通性不变，并且每个连通块都是树。

题目解析

首先我们可以通过询问得到每一条边的边权，总共查询 m 次，每次只需要保留一条边。
我们可以考虑 Kruskal 的方法。
注意到 Kruskal 的做法是将边权从小到大排序，然后判断每一条边是否可以加入到生成树（这题是生成森林）里面。重点在于加入这条边Hi好是否改变图的连通性。
所以我们考虑使用询问操作来判断连通性。
记上一次操作得到的最大生成森林为 las，新加进去的边的边权为 c，那么如果加进去后的边得到的最大生成森林是 las+c，代表这条边加进去后图的连通性改变了，那么就把这条边的边权计入答案。这样需要询问 m 次。
所以总共 2m 次刚刚好。

核心代码：

struct JTZ{
    int c,num;
    bool operator < (const JTZ x) const {
        return this->c < x.c;
    }
}edge[maxn]; int n,m; char ask[maxn];
int main(){
    n=read(); m=read(); int i,j,now,las,ans; las=ans=0;
    for(i=1;i<=m;i++){
        pc('?'),pc(' '); for(j=1;j<=m;j++) pc(i==j?'1':'0'); pc('\n'); fflush(stdout);
        edge[i].c=read(); edge[i].num=i; ask[i]='0';
    } sort(edge+1,edge+m+1);
    for(i=1;i<=m;i++){
        ask[edge[i].num]='1'; printf("? %s\n",ask+1); fflush(stdout);
        now=read(); if(now==las+edge[i].c) ans+=edge[i].c; las=now; 
    } pc('!'),pc(' '),print(ans);
    return 0;
}