CF1687B Railway System 题解

· · 题解

蒟蒻的第一道交互题，第二篇题解，可能写的不好，轻喷。

题目传送门

题意简述

交互题，一个 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;
}