第一行给出三个正整数 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
图的长和宽很大,所以我们不可能把所有点都连边
我们发现没有传送门的点是没有意义的
所以这需要在有传送门的点之间连边即可
一二操作好处理,三号操作的话,因为长和宽很大数组肯定开不下
我们用 map 去记录周围八个点是否有穿送门即可
细节看代码,记得 vector 的内存是根据实际用多少来算的
- #include <bits/stdc++.h>
- #define ll long long
- #define eps 1e-7
- using namespace std;
- inline int read(){
- int x=0;int f=1;char ch=getchar();
- while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
- while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- const int MAXN=1e5+10;
- int dx[8]={0,0,1,1,1,-1,-1,-1};
- int dy[8]={1,-1,0,1,-1,0,1,-1};
- vector < int > a[1000010],b[1000010];
- map < int,int > mp[1000010];
- struct node{
- int y,next;
- }e[1000010],E[1000010];
- int dfs_clock=0,linkk[MAXN],dfn[MAXN],low[MAXN],ans,k,n,m,f[MAXN],x[MAXN],y[MAXN],opt[MAXN],len,Linkk[MAXN],stark[MAXN],top,tot,ine[MAXN],sum[MAXN];
- bool vis[MAXN];
- inline void insert(int xx,int yy){
- if(xx==yy) return;
- e[++len].y=yy;e[len].next=linkk[xx];linkk[xx]=len;
- }
- inline void insertt(int xx,int yy){
- E[++len].y=yy;E[len].next=Linkk[xx];Linkk[xx]=len;
- }
- inline void tarjin(int st){
- dfn[st]=low[st]=++dfs_clock;
- stark[++top]=st;vis[st]=1;
- for(int i=linkk[st];i;i=e[i].next){
- if(!dfn[e[i].y]){
- tarjin(e[i].y);
- low[st]=min(low[st],low[e[i].y]);
- }
- else if(vis[e[i].y]) low[st]=min(low[st],dfn[e[i].y]);
- }
- if(low[st]==dfn[st]){
- tot++;int k;
- do{
- k=stark[top--];
- ine[k]=tot;
- sum[tot]++;
- vis[k]=0;
- }while(k!=st);
- }
- }
- void init(){
- k=read();n=read();m=read();
- for(int i=1;i<=k;i++){
- x[i]=read();y[i]=read();opt[i]=read();
- mp[x[i]][y[i]]=i;
- a[x[i]].push_back(i);
- b[y[i]].push_back(i);
- }
- }
- void build(){
- for(int i=1;i<=n;i++){
- int x=0;int t=a[i].size();
- for(int j=0;j<t;j++){
- if(opt[a[i][j]]==1) {x=a[i][j];break;}
- }
- for(int j=0;j<t;j++){
- insert(x,a[i][j]);
- if(opt[a[i][j]]==1) insert(a[i][j],x);
- }
- }
- for(int i=1;i<=m;i++){
- int y=0;int t=b[i].size();
- for(int j=0;j<t;j++){
- if(opt[b[i][j]]==2) {y=b[i][j];break;}
- }
- for(int j=0;j<t;j++){
- insert(y,b[i][j]);
- if(opt[b[i][j]]==2) insert(b[i][j],y);
- }
- }
- for(int i=1;i<=k;i++){
- if(opt[i]==3){
- for(int j=0;j<8;j++){
- int t=mp[x[i]+dx[j]][y[i]+dy[j]];
- if(t) insert(i,t);
- }
- }
- }
- }
- void rebuild(){
- len=0;
- for(int i=1;i<=k;i++){
- for(int j=linkk[i];j;j=e[j].next){
- if(ine[i]!=ine[e[j].y]){
- insertt(ine[i],ine[e[j].y]);
- }
- }
- }
- }
- inline void dp(int st){
- vis[st]=1;
- for(int i=Linkk[st];i;i=E[i].next){
- if(!vis[E[i].y]) dp(E[i].y);
- f[st]=max(f[E[i].y],f[st]);
- }
- f[st]+=sum[st];
- ans=max(ans,f[st]);
- }
- void solve(){
- build();
- for(int i=1;i<=k;i++){
- if(!dfn[i]) tarjin(i);
- }
- rebuild();
- memset(vis,0,sizeof(vis));
- for(int i=1;i<=tot;i++){
- if(!vis[i]) dp(i);
- }
- cout<<ans<<endl;
- }
- int main(){
- init();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2432288.html