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
在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的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
但是发现可以这样做，对于横天门，每行找出一个横天门，与该行其他横天门连双向边，即表示了这一堆强联通，对于该行的其他门，连单向边，
对于纵寰门同理
对于河蟹门，暴力连边复杂度不会过高
但是如何建图很重要，我们暴力建图，复杂度会达到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; }