Description

Input

Output

Sample Input

?

題解：

　　水題，但還是打表過的……

　　這個題目，我們顯然可以對關鍵點進行加邊。我就是因為加邊加太多了才MLE的，當然對于1,2這兩種類型，用動態數組，對于3，用map或者set判斷十分存在就可以了。

　　當然，然后事情就好辦了，顯然我們可以tarjian一下，記一下每個聯通分量的size，這樣就轉化成了DAG上的最長路。

　　注意最長路一定要用記憶化搜索，不要用spfa，被卡常卡成40分。

?

代碼:

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #include <vector> #include <map> #include <stack> #include <queue> #include <time.h> #define MAXN 100100 using namespace std;struct node{int x,y;bool operator <(const node &a)const{return x==a.x ? y<a.y : x<a.x;} }; struct edge{int first;int next;int to; }a[MAXN*20],b[MAXN*40]; vector<int> hang[MAXN*10],lie[MAXN*10]; map<node,int> mp; int h[MAXN],l[MAXN],id[MAXN],du[MAXN]; int dfn[MAXN],low[MAXN],in[MAXN],size[MAXN],fa[MAXN]; int dis[MAXN],have[MAXN]; stack<int> s; int n,r,c,ans=0;int num=0,tot=0,num2=0,num3=0;void addedge(int from,int to){a[++num].to=to;a[num].next=a[from].first;a[from].first=num;if(num>=MAXN*20){printf("77333");exit(0);} }void tarjian(int now){dfn[now]=low[now]=++num2;in[now]=1;s.push(now);for(int i=a[now].first;i;i=a[i].next){int to=a[i].to;if(!dfn[to]){tarjian(to);low[now]=min(low[now],low[to]);}else if(in[to]) low[now]=min(low[now],dfn[to]);}if(low[now]==dfn[now]){int u=-1;tot++;while(u!=now){u=s.top();s.pop();in[u]=0;fa[u]=tot;size[tot]++;}} }void addedge1(int from,int to){b[++num3].to=to;b[num3].next=b[from].first;b[from].first=num3; }void make(){for(int now=1;now<=n;now++){for(int i=a[now].first;i;i=a[i].next){int to=a[i].to;if(fa[now]!=fa[to]) addedge1(fa[now],fa[to]),du[fa[to]]++;}} }int dfs(int now){if(have[now]) return dis[now];have[now]=1;for(int i=b[now].first;i;i=b[i].next){int to=b[i].to;dis[now]=max(dis[now],dfs(to));}dis[now]+=size[now];ans=max(ans,dis[now]);return dis[now]; }int main() {scanf("%d%d%d",&n,&r,&c);for(int i=1;i<=n;i++){scanf("%d%d%d",&h[i],&l[i],&id[i]);hang[h[i]].push_back(i);lie[l[i]].push_back(i);mp[(node){h[i],l[i]}]=i;}for(int i=1;i<=n;i++){if(id[i]==1) for(int j=0,len=hang[h[i]].size();j<len;j++) addedge(i,hang[h[i]][j]);if(id[i]==2) for(int j=0,len=lie[l[i]].size();j<len;j++) addedge(i,lie[l[i]][j]);if(id[i]==3){int x=h[i],y=l[i];if(mp[(node){x-1,y-1}]) addedge(i,mp[(node){x-1,y-1}]);if(mp[(node){x-1,y}]) addedge(i,mp[(node){x-1,y}]);if(mp[(node){x-1,y+1}]) addedge(i,mp[(node){x-1,y+1}]);if(mp[(node){x,y-1}]) addedge(i,mp[(node){x,y-1}]);if(mp[(node){x,y+1}]) addedge(i,mp[(node){x,y+1}]);if(mp[(node){x+1,y-1}]) addedge(i,mp[(node){x+1,y-1}]);if(mp[(node){x+1,y}]) addedge(i,mp[(node){x+1,y}]);if(mp[(node){x+1,y+1}]) addedge(i,mp[(node){x+1,y+1}]);}}for(int i=1;i<=n;i++) if(!dfn[i]) tarjian(i);make();for(int i=1;i<=tot;i++) if(du[i]==0) dfs(i);printf("%d\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/renjianshige/p/7629818.html

總結

以上是生活随笔為你收集整理的BZOJ 1924 [Sdoi2010]所驼门王的宝藏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。