蒟蒻的第一道交互题,第二篇题解,可能写的不好,轻喷。
题意简述
交互题,一个 $n$ 个点 $m$ 条边的无向带权图。初始给定 $n$,$m$,每次可以询问一个边集,返回由这些边组成的最大生成森林的边权和。要求在 $2m$ 次询问内求出最小生成森林的权值和。
($2 \leq n \leq 200$,$1 \leq m \leq 500$)
题目分析
一个显然的想法,前 $m$ 次询问每次只询问一条边,知道每条边的边权,但还不知道图的形态。
考虑一下 Kruskal 的过程:
-
按边权从小到大排序
-
依次尝试加边,并查集判断是否会成环
我们可以发现,问题就在能否判断环,于是可以考虑能不能通过询问代替并查集的过程。
考虑将新加的边与原来已知的最小生成树(或森林)的边集进行一次询问,其最大生成树(或森林)可能发生了以下几种情况:
- 新加的边与原最大生成树(或森林)构成了环,为了保持连通性,从环上踢掉了一条边权更小的边,边权和变化量小于新加边的边权。
- 新加的边直接加入原最大生成树(或森林),边权和变化量等于新加边的边权。
显然,第一种情况的边是不能选的,因为新加这条边会使得最小生成树(或森林)有环。只有第二种情况满足。
同时不难发现,每次询问后最大生成树(或森林)的形态与最小生成树(或森林)的形态(边和点)都是一致的。这也是能这么做的一个依据。
综上,前 $m$ 次询问得到每条边边权。后 $m-1$ 次询问,每次我们用新加的边与原来已知的最小生成树(或森林)的边集进行一次询问,若边权和变化量小于新加边的边权,则这条边不可选;若边权和变化量等于新加边的边权,则选。这样就能在 $2m$ 次询问内得出答案。
Code
#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;
}