【刷题】BZOJ 1924 [Sdoi2010]所驼门王的宝藏

Description

Input

第一行给出三个正整数 N, R, C。 以下 N 行，每行给出一扇传送门的信息，包含三个正整数xi, yi, Ti，表示该传送门设在位于第 xi行第yi列的藏宝宫室，类型为 Ti。Ti是一个1~3间的整数， 1表示可以传送到第 xi行任意一列的“横天门”，2表示可以传送到任意一行第 yi列的“纵寰门”，3表示可以传送到周围 8格宫室的“自 由 门”。 保证 1≤xi≤R，1≤yi≤C，所有的传送门位置互不相同。

Output

只有一个正整数，表示你确定的路线所经过不同藏宝宫室的最大数目。

Sample Input

10 7 7
2 2 1
2 4 2
1 7 2
2 7 3
4 2 2
4 4 1
6 7 3
7 7 1
7 5 2
5 2 1

Sample Output

9

HINT

测试点编号 N R C 1 16 20 20 2 300 1,000 1,000 3 500 100,000 100,000 4 2,500 5,000 5,000 5 50,000 5,000 5,000 6 50,000 1,000,000 1,000,000 7 80,000 1,000,000 1,000,000 8 100,000 1,000,000 1,000,000 9 100,000 1,000,000 1,000,000 10 100,000 1,000,000 1,000,000

Solution

先考虑最朴素的方法，对于一个宝藏，从它向所有它能到达的点连有向边。于是得到了一个有向有环图，对这个图进行缩点，于是得到一个DAG，我们想要的答案就可以在这个DAG上dp求得
但是这样的边数是 \(O(n^2)\) 的，承受不了。于是考虑对于每一行和每一列建一个超级点，这个超级点可以到达当前列的所有宝藏点。而对于一个宝藏，如果它是第一种门，则将它向它所在的行的超级点连边，第二种门同理，第三种门就直接连能到达的宝藏。这样就把边数降了下来，可以承受
需要注意的是，这种缩完点后还要dp的问题，重新建边的时候要注意重边的问题

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=2100000+10,MAXM=1000000+10,MAXD=100000+10;
int n,r,c,e,snt,cnt,Be[MAXN],DFN[MAXN],LOW[MAXN],f[MAXN],in[MAXN],beg[MAXN],ans,to[MAXM<<1],nex[MAXM<<1],Visit_Num,Stack[MAXN],Stack_Num,In_Stack[MAXN],val[MAXN],dr[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
struct node{
    int x,y,t;
};
node type[MAXD];
struct edge{
    int u,v;
    inline bool operator < (const edge &A) const {
        return u<A.u||(u==A.u&&v<A.v);
    };
    inline bool operator == (const edge &A) const {
        return u==A.u&&v==A.v;
    };
};
edge side[MAXM];
std::queue<int> q;
std::map<int,int> M;
template<typename T> inline void read(T &x)
{
    T data=0,w=1;
    char ch=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
    x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline int id(int x,int y)
{
    return (x-1)*c+y;
}
inline void insert(int x,int y,int opt=1)
{
    if(opt)side[++snt]=(edge){x,y};
    to[++e]=y;
    nex[e]=beg[x];
    beg[x]=e;
}
inline void Tarjan(int x)
{
    DFN[x]=LOW[x]=++Visit_Num;
    In_Stack[x]=1;
    Stack[++Stack_Num]=x;
    for(register int i=beg[x];i;i=nex[i])
        if(!DFN[to[i]])Tarjan(to[i]),chkmin(LOW[x],LOW[to[i]]);
        else if(In_Stack[to[i]]&&DFN[to[i]]<LOW[x])LOW[x]=DFN[to[i]];
    if(LOW[x]==DFN[x])
    {
        int temp;++cnt;
        do{
            temp=Stack[Stack_Num--];
            In_Stack[temp]=0;
            Be[temp]=cnt;
            val[cnt]+=(temp<=n?1:0);
        }while(temp!=x);
    }
}
inline void toposort()
{
    for(register int i=1;i<=cnt;++i)
        if(!in[i])q.push(i),f[i]=val[i];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(register int i=beg[x];i;i=nex[i])
        {
            chkmax(f[to[i]],f[x]+val[to[i]]);
            in[to[i]]--;
            if(!in[to[i]])q.push(to[i]);
        }
    }
}
int main()
{
    read(n);read(r);read(c);
    for(register int i=1;i<=n;++i)
    {
        int x,y,t;read(x);read(y);read(t);
        insert(x+n,i);insert(y+r+n,i);
        M[id(x,y)]=i;
        type[i]=(node){x,y,t};
    }
    for(register int i=1;i<=n;++i)
    {
        int x=type[i].x,y=type[i].y,t=type[i].t;
        if(t==1)insert(i,x+n);
        if(t==2)insert(i,y+r+n);
        if(t==3)
            for(register int k=0;k<8;++k)
            {
                int dx=x+dr[k][0],dy=y+dr[k][1];
                if(M[id(dx,dy)])insert(i,M[id(dx,dy)]);
            }
    }
    for(register int i=1;i<=n+r+c;++i)
        if(!DFN[i])Tarjan(i);
    e=0;memset(beg,0,sizeof(beg));
    for(register int i=1;i<=snt;++i)side[i].u=Be[side[i].u],side[i].v=Be[side[i].v];
    std::sort(side+1,side+snt+1);
    snt=std::unique(side+1,side+snt+1)-side-1;
    for(register int i=1;i<=snt;++i)
        if(side[i].u!=side[i].v)insert(side[i].u,side[i].v,0),in[side[i].v]++;
    toposort();
    for(register int i=1;i<=cnt;++i)chkmax(ans,f[i]);
    write(ans,'\n');
    return 0;
}

【刷题】BZOJ 1924 [Sdoi2010]所驼门王的宝藏

原文：https://www.cnblogs.com/hongyj/p/9517302.html