题解 P4646 【[IOI2007] flood 洪水】

· · 题解

方法来自于djq神仙

对偶图什么的是不会的，这辈子都是不会的

我们把一个房间（四面都有墙的极小密闭空间）抽象成一个节点，并在由一堵墙隔开的两个房间之间连一条边。

我们把城市外围也抽象成一个节点。则从该节点出发，搜出到每个房间的距离。则如果一堵墙两侧的房间到城市外围的距离相等，这堵墙便不会被冲塌。

但是这个方法太恶心了，因为你连各个房间由哪些墙组成都很难找出

所以就有一种方法：

我们把一堵墙拆成两个点i与i'，分别表示墙两侧的连通块；

在每个点处，我们合并它所连接着的墙所对应的连通块。

我们将四个方向分别定为0,2,1,3（绿字），同时令0表示i，1表示i'（蓝字）。则我们要合并(\color{green}{0}\color{blue}0\color{black},\color{green}{2}\color{blue}0\color{black})、(\color{green}{2}\color{blue}1\color{black},\color{green}{1}\color{blue}0\color{black})、(\color{green}{1}\color{blue}1\color{black},\color{green}{3}\color{blue}1\color{black})、(\color{green}{3}\color{blue}0\color{black},\color{green}{0}\color{blue}1\color{black})。当然，也有可能一个点并不在四个方向都有墙——那也不要紧，我们就跳过缺失的墙即可。

而怎么合并呢？你可能会直观地想到并查集——但是我们可以使用01bfs。我们可以在合并的点之间连上一条权值为0的边，并在墙所拆成的两个点之间连一条权值为1的边，然后搜索即可。

则一堵墙可以保留，当且仅当其被拆出的两个点到起点距离相等。

最后，我们如何找到代表城市外围的点呢？

抱歉，这个方法就不太美妙了——对于原图中每个连通块，找到里面y最大的那堵墙，则它拆出来的某个点一定在城市外围上，找到那个点作为bfs起点即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,head[400100],cnt,dir[100100][4],to[100100][4],x[100100],y[100100],S,mxy,dis[400100],tot;
bool vis[100100];
struct edge{
    int to,next,val;
}edge[1001000];
void ae(int u,int v,int w){
//  printf("%d %d %d\n",u,v,w);
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
int ori(int u,int v){
    if(y[u]==y[v])return x[u]>x[v];
    if(x[u]==x[v])return 2+(y[u]>y[v]);
}
void dye(int u){
    vis[u]=true;
    for(int i=0;i<4;i++){
        if(!dir[u][i])continue;
        if((i==0||i==2)&&y[u]>mxy)mxy=y[u],S=dir[u][i];
        if(!vis[to[u][i]])dye(to[u][i]);
    }
}
void bfs(){
    deque<int>q;
    q.push_back(S),dis[S]=0;
    while(!q.empty()){
        int u=q.front();q.pop_front();
//      printf("%d:%d\n",u,dis[u]);
        for(int i=head[u];i!=-1;i=edge[i].next){
            if(dis[edge[i].to]<=dis[u]+edge[i].val)continue;
//          printf("%d->%d:%d\n",u,edge[i].to,edge[i].val);
            dis[edge[i].to]=dis[u]+edge[i].val;
            if(edge[i].val)q.push_back(edge[i].to);
            else q.push_front(edge[i].to);
        }
    }
}
int main(){
    scanf("%d",&n),memset(head,-1,sizeof(head)),memset(dis,0x3f3f3f3f,sizeof(dis));
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
    scanf("%d",&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
//      printf("U,V:%d V,U:%d\n",ori(u,v),ori(v,u));
        dir[u][ori(u,v)]=i,to[u][ori(u,v)]=v;
        dir[v][ori(v,u)]=i,to[v][ori(v,u)]=u;
        ae(i,i+m,1);
    }
    for(int i=1;i<=n;i++){
        vector<int>v;
        if(dir[i][0])v.push_back(0);
        if(dir[i][2])v.push_back(2);
        if(dir[i][1])v.push_back(1);
        if(dir[i][3])v.push_back(3);
        if(v.empty())continue;
        int p,q;
        for(int j=0;j+1<v.size();j++){
            p=v[j],q=v[j+1],ae(dir[i][p]+(p==1||p==2)*m,dir[i][q]+(q==0||q==3)*m,0);
        }
        p=v.back(),q=v.front(),ae(dir[i][p]+(p==1||p==2)*m,dir[i][q]+(q==0||q==3)*m,0);
    }
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        S=0,mxy=-1;
        dye(i);
        if(S)bfs();
    }
    for(int i=1;i<=m;i++)tot+=(dis[i]==dis[i+m]);
//  for(int i=1;i<=2*m;i++)printf("%d:%d\n",i,dis[i]);
    printf("%d\n",tot);
    for(int i=1;i<=m;i++)if(dis[i]==dis[i+m])printf("%d\n",i);
    return 0;
}