Codeforces 1033E. Hidden Bipartite Graph
題目鏈接：1033E - Hidden Bipartite Graph
題目大意：交互題，有一個點數為 \(n\le 600\) 的無向連通圖（\(n\) 給定），有 \(20000\) 次詢問機會。每次詢問可以給出一個點集，返回點集內的點兩兩之間一共有多少條邊。要求判斷圖是否為二分圖，若是則輸出其中一邊，若不是則輸出其中一個奇環。
考慮將圖分層，一開始第一層對應點集 \(S_1={1}\)，之后如果對每一層 \(S_i\)，都能找到所有與 \(S_i\) 有邊相連的點，那么就能有一個新的點集 \(S_{i+1}\)，一直這樣下去就能建起一棵生成樹，實現對圖的分層。
那么現在就需要處理若干個這樣的子問題：有點集 \(S,T\)，要求在 \(T\) 中找到所有與 \(S\) 有邊相連的點。
考慮分治，對點集 \(T\) ，可以把所有點都存在 vector 中，這樣每個區間就對應著 \(T\) 中的一個子集。我們把 \(T\) 分成兩部分 \(T_L=[l,mid],T_R=(mid,r]\)，如果我們能判斷出 \(T_L,T_R\) 與 \(S\) 之間的連邊關系，對有邊的區間繼續詢問下去，就能夠進行遞歸求解求出所有滿足條件的點。
現在相當于我們需要判斷兩個點集 \(S,t\) 之間是否有連邊，那么我們知道，當詢問的點集為 \(S\cup t\) 時，返回的邊數里包含了 \(S\) 內部以及 \(t\) 內部自身的連邊。所以我們相當于要判斷 \(Ask(S\cup t)-Ask(S)-Ask(t)\) 的值。而由于在每一層，\(S\) 都是固定的，所以可以提前存下 \(Ask(S)\) 的值，就可以做到兩次詢問實現判斷了。
我們分析一下這樣做需要耗費的詢問次數。其實可以類比線段樹的單點修改操作，對于所有滿足條件的點，與之相關的區間都只會有 \(O(\log n)\) 個，于是可以得出總的詢問次數就是 \(O(n\log n)\) 的。
現在我們求出了每一層有哪些點，接下去就可以進行判斷。只需要把奇數層和偶數層分別放到一起，判斷內部是否有連邊即可。那么是二分圖的情況非常好弄，直接輸出就好，不是二分圖的情況就不是很好搞，因為我們需要找到一個奇環。
我們知道，出現矛盾是因為奇數層（或偶數層）內部有邊相連，那么如果我們能夠找到這條邊 \((x,y)\)，并找到 \(x\) 與 \(y\) 到這棵生成樹上 \(\operatorname{LCA}(x,y)\) 的路徑，就相當于找到了一個奇環。
那么這里就面臨著兩個問題：
- 怎么找到 \((x,y)\)；
- 怎么找到 \(\operatorname{LCA}(x,y)\)，或者怎么找一個點 \(x\) 在生成樹上的父親。
首先，我們可以通過枚舉集合內部的點 \(i\)，并判斷 \(i\) 與集合內其他點是否有連邊找到其中的一個端點 \(x\)。找到 \(x\) 之后，我們只需要在剩下的集合中找到一個與 \(x\) 相鄰的點即可。
而關于找 \(x\) 在生成樹上的父親，我們可以在分層的時候就可以記錄每個點對應的層數 $v_x $，那么我們只需要找到一個在 \(v_x-1\) 層的一個點與 \(x\) 相鄰即可。如果能實現這一操作，我們就能夠一步步往上跳暴力找到兩個點的 \(\operatorname{LCA}\)。
可以發現，這兩個問題最終都需要我們處理一個操作：給定集合 \(T\) 與點 \(x\)，找到 \(T\) 中任意一個與 \(x\) 有邊相連的點。可以套用之前的做法分治，但是因為這里只需要找到任意一個滿足條件的點，二分查找就足夠了，這一部分所需要的詢問次數也是 \(O(n\log n)\) 的。
于是在最壞情況下，每次操作都需要耗費兩個詢問次數，大概需要詢問 \(4n\log n\) 次，正好卡在 \(20000\) 以內，最后本人代碼的最多詢問次數為 \(16675\)，還是比較充裕的。
#include<bits/stdc++.h>
using namespace std;
#define N 666
int n,cnt,v[N],t;
vector<int>d,s,tmp,O,E,f[N];
int Ask(vector<int>D)//詢問
{
if(D.size()<2)return 0;//點集大小不超過2時，可以不用詢問
printf("? %d\n",(int)D.size());
for(auto i:D)printf("%d ",i);
printf("\n");
fflush(stdout);
int res;
scanf("%d",&res);
return res;
}
int Count(int l,int r)//計算S和區間[l,r]內的點之間的邊數
{
tmp.clear();
for(int i=l;i<=r;i++)tmp.push_back(d[i]);
int Self=Ask(tmp);//計算[l,r]內部邊數
for(auto i:s)tmp.push_back(i);
int Sum=Ask(tmp);//計算并集的總邊數
return Sum-Self-t;//t的值在之前已經提前求過了，是S內部的邊數
}
void Find(int l,int r)//利用分治的思想找到每個與S有連邊的點
{
if(l==r){
if(Count(l,r)){//單獨判斷d[l]與S是否有連邊
v[d[l]]=cnt;//v[i]表示i號結點在第幾層
f[cnt].push_back(d[l]);//把每一層的結果存下來，后面找父親要用
}
return;
}
int mid=l+r>>1;//這里的操作和線段樹單點修改類似
if(Count(l,mid))Find(l,mid);
if(Count(mid+1,r))Find(mid+1,r);
}
int Find2()//已知點x與d內的點有連邊，二分找出一個與x有連邊的點
{
int l=0,r=d.size()-1;
while(l<r){
int mid=l+r>>1;
if(Count(l,mid))r=mid;
else l=mid+1;
}
return d[l];
}
int getf(int x)//對于點x，在樹上的父親一定在v[x]-1這一層
{
t=0;
d=f[v[x]-1];
s.clear();
s.push_back(x);
return Find2();
}
void rua(vector<int>D)//找奇環
{
int m=D.size(),x,y;
for(int i=0;i<m;i++){//通過枚舉找到一個與其他點有連邊的x
tmp.clear();
for(int j=0;j<m;j++)
if(j!=i)tmp.push_back(D[j]);
if(Ask(tmp)<t){
x=D[i];
break;
}
}
t=0;
d=tmp;
s.clear();
s.push_back(x);
y=Find2();//找到一個與x有連邊的y
vector<int>ansx,ansy;//分別存儲x,y到其祖先的路徑，直接暴力找LCA
ansx.push_back(x);
ansy.push_back(y);
while(v[x]<v[y]){
x=getf(x);
ansx.push_back(x);
}
while(v[y]<v[x]){
y=getf(y);
ansy.push_back(y);
}
while(x!=y){
x=getf(x);
y=getf(y);
ansx.push_back(x);
ansy.push_back(y);
}
printf("N %d\n",ansx.size()+ansy.size()-1);
for(auto i:ansx)printf("%d ",i);
ansy.pop_back();
reverse(ansy.begin(),ansy.end());//因為之前輸出的是x到LCA的路徑，所以要翻轉
for(auto i:ansy)printf("%d ",i);
}
int main()
{
scanf("%d",&n);
v[1]=++cnt;
s.push_back(1);
f[1].push_back(1);
for(int i=2;i<=n;i++)d.push_back(i);
while(!d.empty()){
cnt++;
t=Ask(s);//提前計算S內部的連邊，減少詢問次數
Find(0,d.size()-1);
d.clear(),s.clear();
for(int i=1;i<=n;i++){
if(!v[i])d.push_back(i); //所有還沒訪問過的點作為集合T
if(v[i]==cnt)s.push_back(i);//把當前層的點作為新的S
}
}
for(int i=1;i<=n;i++)//奇偶分別存，判斷是否存在奇環
if(v[i]&1)O.push_back(i);
else E.push_back(i);
t=Ask(O);
if(t){
rua(O);
return 0;
}
t=Ask(E);
if(t){
rua(E);
return 0;
}
printf("Y %d\n",(int)O.size());
for(auto i:O)printf("%d ",i);
return 0;
}
浙公網安備 33010602011771號