CF1687B Railway System 题解

蒟蒻的第一道交互题，第二篇题解，可能写的不好，轻喷。 [题目传送门](https://www.luogu.com.cn/problem/CF1687B) ## 题意简述 交互题，一个 $n$ 个点 $m$ 条边的无向带权图。初始给定 $n$，$m$，每次可以询问一个边集，返回由这些边组成的最大生成森林的边权和。要求在 $2m$ 次询问内求出最小生成森林的权值和。 （$2 \leq n \leq 200$，$1 \leq m \leq 500$） ## 题目分析 一个显然的想法，前 $m$ 次询问每次只询问一条边，知道每条边的边权，但还不知道图的形态。 考虑一下 Kruskal 的过程： - 按边权从小到大排序 - 依次尝试加边，并查集判断是否会成环 我们可以发现，问题就在能否判断环，于是可以考虑能不能通过询问代替并查集的过程。 考虑将新加的边与原来已知的最小生成树（或森林）的边集进行一次询问，其最大生成树（或森林）可能发生了以下几种情况： - 新加的边与原最大生成树（或森林）构成了环，为了保持连通性，从环上踢掉了一条边权更小的边，**边权和变化量小于新加边的边权**。 - 新加的边直接加入原最大生成树（或森林），**边权和变化量等于新加边的边权**。 显然，第一种情况的边是不能选的，因为新加这条边会使得最小生成树（或森林）有环。只有第二种情况满足。 同时不难发现，每次询问后最大生成树（或森林）的形态与最小生成树（或森林）的形态（边和点）都是一致的。这也是能这么做的一个依据。 综上，前 $m$ 次询问得到每条边边权。后 $m-1$ 次询问，每次我们用新加的边与原来已知的最小生成树（或森林）的边集进行一次询问，若边权和变化量小于新加边的边权，则这条边不可选；若边权和变化量等于新加边的边权，则选。这样就能在 $2m$ 次询问内得出答案。 ## Code ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=505; int n,m; bool bj[maxn]; //记录已知最小生成树（或森林）的边 struct edge{ int p,v; }c[maxn]; bool cmp(edge x,edge y){ return x.v<y.v; } int main(){ ios::sync_with_stdio(0); cin>>n>>m; for(int i=1;i<=m;i++){ cout<<"? "; for(int j=1;j<=m;j++){ if(j!=i)cout<<bj[i]; else cout<<1; } cout<<endl; fflush(stdout); c[i].p=i; cin>>c[i].v; } sort(c+1,c+1+m,cmp); int cnt=0; ll ans=0; int x=c[1].v,y; bj[c[1].p]=1; ans+=c[1].v; for(int i=2;i<=m;i++){ cout<<"? "; bj[c[i].p]=1; for(int j=1;j<=m;j++){ cout<<bj[j]; } cout<<endl; fflush(stdout); cin>>y; int d=y-x; if(d<c[i].v){ //若边权和变化量小于新加边的边权，不选 bj[c[i].p]=0; } else{ ans+=c[i].v; x=y; if(++cnt==n-1)break; } } cout<<"! "<<ans; return 0; } ```