文章目錄

• 題目描述
• 解析
• 代碼

洛谷傳送門(mén)

題目描述

解析

看題目要求很容易想到強(qiáng)連通分量縮點(diǎn)加拓?fù)鋎p
但是問(wèn)題在于存圖

第一感就是和暴力和每個(gè)點(diǎn)連邊
但那樣無(wú)論點(diǎn)數(shù)和邊數(shù)都很爆炸

隨后我們發(fā)現(xiàn)這個(gè)圖非常稀疏
所以我們可以只連有寶藏的點(diǎn)
然而這樣邊數(shù)會(huì)被一行橫門(mén)這樣的數(shù)據(jù)卡成n²
怎么辦呢？
------我的思路到這里就結(jié)束了，下面是題解內(nèi)容---------
類(lèi)似于電話(huà)的原理
如果新加一臺(tái)電話(huà)就和其他所有電話(huà)連線(xiàn)，線(xiàn)會(huì)非常多
所以就有了轉(zhuǎn)線(xiàn)站，新電話(huà)只需要和它相連就行了
本題也是類(lèi)似的思路
真正建邊的瓶頸在于橫門(mén)和豎門(mén)
所以就每行和每列建一個(gè)代表點(diǎn)，連向該行（列）的所有寶藏室
橫（豎）門(mén)就與本行（列）的代表點(diǎn)相連即可
大大減少了連邊條數(shù)
（盡管如此，在洛谷的數(shù)據(jù)范圍中，數(shù)組空間還是要精打細(xì)算。。。）
（也小心很多數(shù)組會(huì)縮點(diǎn)前后用兩遍大小要乘2，不要RE！）

代碼

#include <bits/stdc++.h> using namespace std; #define ll long long const int N=4e6+2e5+100; const int M=3e5+100; int n,m,k; int x[M],y[M],tp[M],v[N]; map<int,map<int,int> >mp;//1-n:行 n+1-n+m：列 int dx[9]={0,-1,-1,-1,0,0,1,1,1}; int dy[9]={0,-1,0,1,-1,1,-1,0,1}; struct node{int to,nxt; }p[N]; int cnt=-1,fi[N]; void addline(int x,int y){ // printf(" add:x=%d y=%d\n",x,y);p[++cnt]=(node){y,fi[x]};fi[x]=cnt; } int id;int dfn[N],low[N],col[N],size[N],tot,tim,zhan[N],top; void tarjan(int x){dfn[x]=low[x]=++tim;zhan[++top]=x;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(!dfn[to]){tarjan(to);low[x]=min(low[x],low[to]);}else if(!col[to]) low[x]=min(low[x],dfn[to]);}if(dfn[x]==low[x]){tot++;while(zhan[top]!=x){size[tot]+=v[zhan[top]];col[zhan[top--]]=tot;}col[x]=tot;size[tot]+=v[x];top--;}return; }int ru[N],dp[N]; void topu(){queue<int>q;for(int i=id+1;i<=tot;i++){dp[i]=size[i];if(!ru[i]) q.push(i); } while(!q.empty()){int now=q.front();q.pop();for(int i=fi[now];~i;i=p[i].nxt){int to=p[i].to;dp[to]=max(dp[to],dp[now]+size[to]);if(--ru[to]==0) q.push(to);}}return; }int main(){memset(fi,-1,sizeof(fi)); // memset(v,0,sizeof(v)); // printf("%d",sizeof(ru)/1024/1024);scanf("%d%d%d",&k,&n,&m);id=n+m;for(int i=1;i<=k;i++){id++;scanf("%d%d%d",&x[i],&y[i],&tp[i]);mp[x[i]][y[i]]=id;addline(x[i],id);addline(n+y[i],id);v[id]=1;}for(int i=n+m+1;i<=id;i++){int xx=x[i-n-m],yy=y[i-n-m];if(tp[i-n-m]==1) addline(i,x[i-n-m]);else if(tp[i-n-m]==2) addline(i,n+y[i-n-m]);else{for(int j=1;j<=8;j++){int nx=xx+dx[j],ny=yy+dy[j];if(nx<0||nx>n||ny<0||ny>m) continue;if(mp[nx][ny]) addline(i,mp[nx][ny]);}}}tot=id;for(int i=1;i<=id;i++){if(!dfn[i]) tarjan(i);} // for(int i=n+m+1;i<=id;i++){ // printf("i=%d col=%d size=%d\n",i-n-m,col[i],size[col[i]]); // }for(int i=1;i<=id;i++){int aa=col[i],bb;for(int j=fi[i];~j;j=p[j].nxt){ // printf("i=%d j=%d\n",i,p[j].to);bb=col[p[j].to];if(aa!=bb) addline(aa,bb),ru[bb]++;}}topu();int ans=0;for(int i=id+1;i<=tot;i++) ans=max(ans,dp[i]);printf("%d",ans);return 0; } /* 10 7 7 2 2 1 2 4 2 1 7 2 2 7 3 4 2 2 4 4 1 6 7 3 7 7 1 7 5 2 5 2 1 */

總結(jié)

以上是生活随笔為你收集整理的P2403 [SDOI2010]所驼门王的宝藏（强连通分量）（拓扑排序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。