首页 > 代码库 > [AMPPZ 2013]Bytehattan

[AMPPZ 2013]Bytehattan

2024-07-16 19:51:40   212人阅读

题目大意：有一个网格图，每次可以炸掉炸掉网格图中的一条边(u, v)。之后他会尝试从u走到v。

如果他成功地从u走到v，他会很高兴；否则他会找人打架。

从第二次爆炸开始，根据此时心情的不同，会炸掉不同的边。

注意此题是强制在线！！！！

对于这种题目，裸的并查集显然是不对的（虽然可以对50分，部分分），但显然不是最优的，听完题解以后，它是一种变相的并查集。

我们维护定义并查集的每一个节点就是网格图中的
每一个方格和最外面的“世界”。一开始他们互不相连，每次如果某条边断了，那么就会有两个方格或方格和世界相连，那么我们就将这两样东西连在一起，如果我们发现出现了一个环（及没连接之前就已经在一个联通块中），那么就是不能从u走到v，因为这一块已经与世隔绝了，所以不可能再想通，否则即为可以走到。

此题思想极好.(因为某位会miao的人http://www.cnblogs.com/dyllalala/p/3903311.html觉得图画的太丑，就不上图了，因为他画的特别好）

#include<iostream>#include<cstdio>using namespace std;int R;int father[500*600];int n;int now;int getId(int x, int y){    if ((x == 0) || (x == R)) return 0;    if ((y == 0) || (y ==R)) return 0;    return (x - 1) * (R - 1) + y;}int find(int x){    if(father[x]==x)return x;    return father[x]=find(father[x]);}void UNION(int x,int y){    father[find(x)]=find(y);}void did(int x1,int y1,int x2,int y2){    if(x1>x2)swap(x1,x2);    if(y1>y2)swap(y1,y2);    int x,y;    if(x1==x2)    {        x=getId(x1- 1,y1);        y=getId(x1, y1);    }    else    {        x=getId(x1, y1- 1);        y=getId(x1, y1);    }    if(find(x)==find(y))    {        now=1;        puts("DAJIA");    }    else    {        now=0;        puts("HAHA");        UNION(x,y);    }    return ;}        int main(){    scanf("%d",&R);    scanf("%d",&n);    for(int i=1;i<=R*R;i++)    father[i]=i;    int x1,x2,y1,y2,x3,y3,x4,y4;    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);    for(int i=1;i<=n;i++)    {        if(now==0)        {            did(x1,y1,x2,y2);        }        else        {            did(x3,y3,x4,y4);        }        if(i!=n)        {            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);            scanf("%d%d%d%d",&x3,&y3,&x4,&y4);        }    }    return 0;}
View Code


联系
我们