这个思路应该是错的,但是不知道哪里错了,或者有没有小一点的hack.
思路如下: 先将点分成 t+1 层,然后将每个点拆成入点和出点,对于两层之间的连边,比如是1,3 就把上一层1的出点和下一层3的入点合并成1个点(上层3和下层1也要合并),然后建立图跑网络流
和正解的主要区别就是:我的是把点直接合并成一个点,正解是建立边
提交记录 https://www.luogu.com.cn/record/112601282
建立边代码如下:
void merge(int c,int d){
int xx=getfa(a[c].y),yy=getfa(a[d].x);
if(xx!=yy){
fa[xx]=yy;
}
}
int main(){
tt=read(),n=read();
for(int i=1;i<=n*tt+n;i++){
a[i].x=2*i-1,a[i].y=2*i;//拆点
}
for(int i=1;i<=2*n*tt+2*n;i++) fa[i]=i;
//用并查集维护每个节点
memset(head,-1,sizeof head);
for(int i=1;i<=tt;i++){
int m=read();
for(int j=1;j<=m;j++){
int a=read(),b=read();
merge((i-1)*n+a,i*n+b);//合并中间点
merge((i-1)*n+b,i*n+a);//上下层的点
}
}
for(int i=2;i<=n;i++){//把第一层的所有入点合并成一个源点
int xx=getfa(a[1].x),yy=getfa(a[i].x);
if(xx!=yy) fa[yy]=xx;
}for(int i=n*tt+2;i<=n*tt+n;i++){//把t+1层的所有出点合并成汇点
int xx=getfa(a[n*tt+1].y),yy=getfa(a[i].y);
if(xx!=yy) fa[yy]=xx;
}
for(int i=1;i<=2*n*tt+2*n;i++){
if(fa[i]==i) number[i]=++tot;
//给新图中的点编号
}s=number[getfa(a[1].x)];t=number[getfa(a[n*tt+n].y)];//源点和汇点
for(int i=1;i<=n*tt+n;i++){
int xx=number[getfa(a[i].x)],yy=number[getfa(a[i].y)];
addedge(xx,yy);//正向和反向弧都有
}