bzoj 1804: [Ioi2007]Flood 洪水

.

题意：好难概括。。自己看吧
题解：对偶图+bfs
一面墙要不倒，就是它两边碰到水的时间是相同的。所以我们可以把原图转为对偶图，一面墙要不倒，对应的边的两个端点到【表示外面的点】的距离要相同。这个bfs一下就好了。重点就是如何转成对偶图。我们从每个点开始走，能往左转就左转，左转不行再直走，再不行再右转，再不行就往回走。这样就可以框出每个块。走的时候记录一下这一块的编号，最后通过墙来建边。
还有一种方法不用转对偶图：每次找最左边的点，然后尽量绕着外围走，绕完删掉这些边。重复这个过程直到没有边。走了两次的边就是不会倒的。这个方法比上面的要慢，要套个log
代码：

#include<bits/stdc++.h>
#define S 0
#define E 1
#define N 2
#define W 3
using namespace std;
int n,w,nn=0,num=0,fst[100010],dis[100010];
struct pnt
{
    int x,y,wall[4],idl[4],idr[4];
}p[100010];
struct edge
{
    int x,y,n;
}e[800010];
bool out[100010];
void add(int x,int y)
{
    if(p[x].x==p[y].x)
    {
        if(p[x].y<p[y].y)
        {
            p[x].wall[E]=y;
            p[y].wall[W]=x;
        }
        else
        {
            p[x].wall[W]=y;
            p[y].wall[E]=x;
        }
    }
    else
    {
        if(p[x].x<p[y].x)
        {
            p[x].wall[S]=y;
            p[y].wall[N]=x;
        }
        else
        {
            p[x].wall[N]=y;
            p[y].wall[S]=x;
        }
    }
}
inline int left(int x)
{
    return (x+1)%4;
}
inline int right(int x)
{
    return (x-1+4)%4;
}
inline int back(int x)
{
    return (x+2)%4;
}
void wk(int x)
{
    for(int i=0;i<4;i++)
    {
        if(p[x].wall[i]&&!p[x].idl[i])
        {
            nn++;
            int cs=0;
            bool tf=1;
            for(int y=x,j=i,z;y!=x||tf;y=z)
            {
                tf=0;
                z=p[y].wall[j];
                p[y].idl[j]=p[z].idr[back(j)]=nn;
                j=left(j);
                cs--;
                while(!p[z].wall[j])
                {
                    j=right(j);
                    cs++;
                }
            }
            if(cs>0)
            out[nn]=1;
        }
    }
}
void ins(int x,int y)
{
    e[++num]={x,y,fst[x]};
    fst[x]=num;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&p[i].x,&p[i].y);
    scanf("%d",&w);
    for(int i=0;i<w;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++)
    wk(i);
    for(int i=1;i<=n;i++)
    for(int j=0;j<4;j++)
    if(p[i].wall[j])
    {
        ins(p[i].idl[j],p[i].idr[j]);
        ins(p[i].idr[j],p[i].idl[j]);
    }
    queue<int>q;
    for(int i=1;i<=nn;i++)
    if(out[i])
    {
        q.push(i);
        dis[i]=1;
    }
    while(!q.empty())
    {
        int x=q.front();
        for(int i=fst[x];i;i=e[i].n)
        {
            int y=e[i].y;
            if(!dis[y])
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
        q.pop();
    }
    int ans=0;
    for(int i=1;i<=num;i+=2)
    if(dis[e[i].x]==dis[e[i].y])
    ans++;
    printf("%d",ans>>1);
}