第一行给出三个正整数 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
思路：
1、对于这个题来说，一开始的大方向思路还是比较好建立的。
对于这个题来讲，一个R*C大小的图，有三种门进行传送，一共最多有1e6个门，那么我们不难将思维划到求最长路上边来，而且是一个没有固定源点的最长路。
考虑求一个多源最短路的时间复杂度，对于1e6个点来讲，肯定是不科学的，而且这个题可能会涉及到环路，所以我们肯定不能直接建好图之后就跑最长路。
无论是什么做法去解这个题，那么首先我们肯定是要建好图之后缩点的。
2、那么对于建图，如果直接暴力扫建图的话是O(n^2)的时间复杂度，那么我们考虑每一种门的特性来建图：
①对于种类1，我们将所有点都分行来存，对每一行去建图。然而对于一种极限情况，如果一行中包含了全部的点，那么时间复杂度还是O(N^2);
此时考虑到强连通的特性，其实我们对于一行的种类1的门来讲，其实只要一个代表去建图就好了，因为对于一行的种类1的门，他们肯定属于同一个强连通分量。
②对于种类2，我们将所有点都分列来存，对每一列去建图，同理，我们对于每一列的种类2的门，都拿出一个代表去建图就好。
③对于钟雷3的门，我们直接将其和上一行的，这一行的，和下一行的点进行判断，如果相距的列距离为1，那么就可以建有向边。
这样的建图显然是比较好的方法了。（其实对于种类3的门，我们还可以对每一行二分去建图，但是好像没必要，我跑的结果是2000+ms）；
3、那么对于建好的图，我们Tarjan强连通缩点，在缩点之后，我们得到了一个DAG图。
那么如果我们已经得到了一个DAG图，而且此时求一条最长路。那么我们不妨在DAG图上用拓扑排序的方法来Dp出来到达每一个点的最长路。
设定dp【v】表示到达点v的最长路。那么有：dp【v】=max（dp【u】+a【u】）；这里a【i】表示编号为u的强连通分量中有多少个点。
那么过程维护一下dp数组即可。
ans=max（dp【i】）【1<=i<=scc 】
Ac代码：
#include<stdio.h>#include<string.h>#include<vector>#include<algorithm>#include<queue>using namespace std;struct node2{ int from; int to; int next;}e[2200600];int fx[8]={1,-1,0,0,1,-1,1,-1};int fy[8]={0,0,1,-1,1,-1,-1,1};struct node{ int x,y; int op,num;}now,nex;int cont;int x[1200600];int y[1200600];int opp[1200600];vector<int >mp[1020060];vector<node >s2[1020060];vector<node >s[1200600];int degree[1000060];int head[1000060];int dfn[1000500];int low[1005000];int stack[1000500];int color[1000500];int vis[1005000];int dp[1000500];int a[1000600];int n,r,c;int tot,cnt,sig;void add(int from,int to){ // PRintf("%d %d/n",from,to); mp[from].push_back(to);}void add2(int from,int to){ // printf("add2:------->%d %d/n",from,to); e[cont].to=to; e[cont].next=head[from]; head[from]=cont++;}void Getmap(){ for(int i=1;i<=n;i++)mp[i].clear(); for(int i=1;i<=r;i++) { int first=-1; for(int j=0;j<s[i].size();j++) { now=s[i][j]; if(now.op==1&&first==-1) { first=now.num; for(int z=0;z<s[i].size();z++) { nex=s[i][z]; if(now.num==nex.num)continue; else { add(now.num,nex.num); if(nex.op==1)add(nex.num,now.num); } } break; } } } for(int i=1;i<=c;i++) { int first=-1; for(int j=0;j<s2[i].size();j++) { now=s2[i][j]; if(now.op==2&&first==-1) { first=now.num; for(int z=0;z<s2[i].size();z++) { nex=s2[i][z]; if(now.num==nex.num)continue; else { add(now.num,nex.num); if(nex.op==2)add(nex.num,now.num); } } break; } } } for(int i=1;i<=n;i++) { if(opp[i]==3) { int xx=x[i]-1; int size=s[xx].size(); for(int j=0;j<size;j++) { now=s[xx][j]; if(abs(now.y-y[i])<=1)add(i,now.num); } xx=x[i]; size=s[xx].size(); for(int j=0;j<size;j++) { now=s[xx][j]; if(abs(now.y-y[i])<=1)add(i,now.num); } xx=x[i]+1; size=s[xx].size(); for(int j=0;j<size;j++) { now=s[xx][j]; if(abs(now.y-y[i])<=1)add(i,now.num); } } }}void init(){ sig=0; cnt=1; tot=-1; cont=0; memset(degree,0,sizeof(degree)); memset(color,0,sizeof(color)); memset(stack,0,sizeof(stack)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(vis,0,sizeof(vis));}void Dp_top(){ memset(dp,0,sizeof(dp)); queue<int >s; for(int i=1;i<=sig;i++) { if(degree[i]==0) { dp[i]=a[i]; s.push(i); } } int output=0; while(!s.empty()) { int u=s.front(); s.pop(); for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; dp[v]=max(dp[u]+a[v],dp[v]); degree[v]--; if(degree[v]==0)s.push(v); } } for(int i=1;i<=sig;i++)output=max(output,dp[i]); //printf("ans:%d/n",output); printf("%d/n",output);}void Tarjan(int u){ vis[u]=1; dfn[u]=low[u]=cnt++; stack[++tot]=u; for(int i=0; i<mp[u].size(); i++) { int v=mp[u][i]; if(vis[v]==0)Tarjan(v); if(vis[v]==1)low[u]=min(low[u],low[v]); } if(dfn[u]==low[u]) { sig++; do { color[stack[tot]]=sig; vis[stack[tot]]=-1; } while(stack[tot--]!=u); }}void Slove(){ init(); for(int i=1;i<=n;i++) { if(vis[i]==0)Tarjan(i); } //printf("SCC:%d/n",sig); cont=0; memset(head,-1,sizeof(head)); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { a[color[i]]++; for(int j=0;j<mp[i].size();j++) { int v=mp[i][j]; if(color[i]!=color[v]) { add2(color[i],color[v]); degree[color[v]]++; } } } /* for(int i=1;i<=sig;i++) { printf("%d %d/n",i,a[i]); }*/ Dp_top();}int main(){ while(~scanf("%d%d%d",&n,&r,&c)) { for(int i=1;i<=r;i++)s[i].clear(); for(int i=1;i<=c;i++)s2[i].clear(); for(int i=1;i<=n;i++) { scanf("%d%d%d",&x[i],&y[i],&opp[i]); now.op=opp[i]; now.num=i; now.x=x[i]; now.y=y[i]; s[x[i]].push_back(now); s2[y[i]].push_back(now); } Getmap(); Slove(); }}
新闻热点
疑难解答
