nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

bzoj1924

题意：

        在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖，外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐，他曾亲自率军粉碎河蟹帝国主义的野蛮侵略，为族人立下赫赫战功。所驼门王一生财宝无数，但因其生性节俭低调，他将财宝埋藏在自己设计的地下宫殿里，这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙，而又非常聪明，他费尽心机谋划了这次盗窃行动，破解重重机关后来到这座地下宫殿前。
        整座宫殿呈矩阵状，由R×C间矩形宫室组成，其中有N间宫室里埋藏着宝藏，称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔，由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门，没有宝藏的宫室不设传送门，所有的宫室传送门分为三种：
        “横天门”：由该门可以传送到同行的任一宫室；
        “纵寰门”：由该门可以传送到同列的任一宫室；
        “自*河蟹*由*河蟹*门”：由该门可以传送到以该门所在宫室为中心周围8格中任一宫室（如果目标宫室存在的话）。
        深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册，书册上详细记录了每扇传送门所属宫室及类型。而且，虽然宫殿内外相隔，但他自行准备了一种便携式传送门，可将自己传送到殿内任意一间宫室开始寻宝，并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次，且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制，每间宫室也可以多次出入。
        现在Henry已经打开了便携门，即将选择一间宫室进入。为得到尽多宝藏，他希望安排一条路线，使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。

输入：
        第一行给出三个正整数 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，所有的传送门位置互不相同。
测试点编号：
        
        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  

强连通缩点后跑spfa最长路即可
但是如何建图很重要，我们暴力建图，复杂度会达到n^2
但是发现可以这样做，对于横天门，每行找出一个横天门，与该行其他横天门连双向边，即表示了这一堆强联通，对于该行的其他门，连单向边，
对于纵寰门同理
对于河蟹门，暴力连边复杂度不会过高

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<map>

using namespace std;

struct Graph{
    static const int maxn=1e5+5,maxm=maxn*8+maxn*2+maxn*2+maxn*8;// 3号节点最多 n*8  ； 1/2号节点 最多双向边n*2  
    struct star{int v,w,nex;} edge[maxm];
    int head[maxn],cnt,n;
    void ini(int n){
        this->n=n; cnt=-1;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void add_edge(int u,int v,int w){
        edge[++cnt]=star{v,w,head[u]}; head[u]=cnt;
    }
};

struct Tarjan:Graph{//强连通分量缩点
    int low[maxn],dfn[maxn],belong[maxn],stk[maxn],instk[maxn],block[maxn];
    int step,color;
    void tarjan(){
        step=color=0;
        for(int i=0;i<=n;i++) dfn[i]=0;
        for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,0);//多个联通快
    }
    void tarjan(int u,int father=0){//此函数不开放
        low[u]=dfn[u]=++step; stk[++stk[0]]=u;instk[u]=1;
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(dfn[v]) {
                if(instk[v]) low[u]=min(low[u],dfn[v]);
            }
            else{
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
            }
        }
        if(low[u]==dfn[u]){
            block[color+1]=1;
            while(stk[stk[0]]!=u) {
                belong[stk[stk[0]]]=color+1;
                instk[stk[stk[0]--]]=0;
                block[color+1]++;
            }
            belong[stk[stk[0]]]=++color;
            instk[stk[stk[0]--]]=0;
        }
    }
}graph;

struct Spfa:Graph{
    int d[maxn],inq[maxn];
    void short_path(int s,int*dist){
        for(int i=0;i<=n;i++) dist[i]=1e9;
        dist[s]=0;
        deque<int>q;
        q.push_back(s);
        inq[s]=1;
        long long sum=0;
        while(!q.empty()){
            int u=q.front(); q.pop_front(); sum-=dist[u];inq[u]=0;
            if(1ll*dist[u]*q.size()>sum){//large label last
                sum+=dist[u];
                q.push_back(u);
                inq[u]=1;
            }
            else{
                for(int i=head[u];~i;i=edge[i].nex){
                    int v=edge[i].v, w=edge[i].w;
                    if(dist[v]>dist[u]+w){
                        if(inq[v]){
                            sum-=dist[v];
                            dist[v]=dist[u]+w;
                            sum+=dist[v];
                        }
                        else{
                            dist[v]=dist[u]+w;
                            inq[v]=1;
                            sum+=dist[v];
                            if(dist[v]<dist[q.front()]) q.push_front(v);//small lable first
                            else q.push_back(v);
                        }
                    }
                }
            }
        }
    }
}g;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

const int maxn=1e6+100;
vector<int>row[maxn],col[maxn];
vector<int>Row[maxn],Col[maxn];
struct node{int x,y;};
vector<node>block;

map<long long,int>mp;
int getid(int x,int y){
    static int cnt=0;
    long long t=x*1e6+y;
    if(mp[t]!=0) return mp[t];
    else return mp[t]=++cnt;
}
bool have(int x,int y){
    long long t=x*1e6+y;
    return mp.find(t)!=mp.end();
}

int bound[8][2]={-1,-1, -1,0, -1,1, 0,-1, 0,1, 1,-1, 1,0, 1,1};

int main(){
    int n=read();
    int r=read();
    int c=read();
    graph.ini(n);
    for(int i=0;i<n;i++){
        int u=read();
        int v=read();
        int t=read();
        getid(u,v);

        if(t==1) {
            col[v].push_back(u);
            Row[u].push_back(v);
        }
        else if(t==2) {
            row[u].push_back(v);
            Col[v].push_back(u);
        }
        else{
            row[u].push_back(v);
            col[v].push_back(u);
            block.push_back(node{u,v});
        }
    }

    //1
    for(int i=0;i<=r;i++){
        if(!Row[i].empty()){
            int quick=getid(i,Row[i][0]);
            for(int t=1;t<Row[i].size();t++){
                int quickkk=getid(i,Row[i][t]);
                graph.add_edge(quick,quickkk,1);
                graph.add_edge(quickkk,quick,1);
            }
            for(int t=0;t<row[i].size();t++){
                graph.add_edge(quick,getid(i,row[i][t]),1);
            }
        }
    }

    //2
    for(int i=0;i<=c;i++){
        if(!Col[i].empty()){
            int quick=getid(Col[i][0],i);
            for(int t=1;t<Col[i].size();t++){
                int quickkk=getid(Col[i][t],i);
                graph.add_edge(quick,quickkk,1);
                graph.add_edge(quickkk,quick,1);
            }
            for(int t=0;t<col[i].size();t++){
                graph.add_edge(quick,getid(col[i][t],i),1);
            }
        }
    }

    //3
    for(int i=0;i<block.size();i++){
        int u=block[i].x;
        int v=block[i].y;
        int quick=getid(u,v);
        for(int j=0;j<8;j++){
            int uu=u+bound[j][0];
            int vv=v+bound[j][1];
            if(have(uu,vv)){
                graph.add_edge(quick,getid(uu,vv),1);
            }
        }
    }

    graph.tarjan();

    g.ini(graph.color+1);

    set<long long>se;
    for(int u=1;u<=graph.n;u++){
        for(int i=graph.head[u];~i;i=graph.edge[i].nex){
            int v=graph.edge[i].v;
            int uu=graph.belong[u];
            int vv=graph.belong[v];
            if(uu==vv) continue;
            long long hash=uu*1e6+vv;
            if(se.find(hash)!=se.end()) continue;
            se.insert(hash);
            g.add_edge(uu,vv,-graph.block[vv]);
        }
    }

    int s=graph.color+1;
    for(int i=1;i<=graph.color;i++) g.add_edge(s,i,-graph.block[i]);
    g.short_path(s,g.d);


    int ans=0;
    for(int i=1;i<=graph.color;i++) ans=min(ans,g.d[i]);
    cout<<abs(ans)<<endl;

}