第一行給出三個正整數 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(); }}
新聞熱點
疑難解答
