[Sdoi2010 所驼门王的宝藏]强连通分量、猥琐优化

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1924
【算法分析】
一开始就YY裸的强连通,但是如果他们都在同一行,而且都是1的话,边数将达到n*n的级别。
然后除了这个猥琐数据,其它的一般好像没啥问题。
于是我就把在同一行的,都是1的用k条边直接连成一个圈。
在同一列的,都是2的,也用k条边直接连成一个圈。
(k表示这一行(列)为1(2)的点的个数。)
然后暴力SCC。
最后dp输出即可。
【其它】
来BS我吧。。。再一次全世界最慢。终于把Sdoi第一轮的6题都AC了~
1 23185 root 7804K 1012MS G++ 3.07K 2010-05-14 13:51:35 2 24544 maja 35592K 1041MS Pascal 3.82K 2010-05-20 09:12:35 3 24545 wu3412790 35592K 1057MS Pascal 3.82K 2010-05-20 09:13:00 4 24621 colonnello 15012K 1153MS Pascal 8.31K 2010-05-20 16:37:08 5 24566 Ksloverainboy 35700K 1167MS Pascal 5.66K 2010-05-20 12:56:19 6 23589 nehzilrz 20024K 1183MS G++ 3.71K 2010-05-16 13:52:20 7 23192 FDhyc 10932K 1232MS Pascal 5.61K 2010-05-14 13:57:22 8 23362 oimaster 11568K 1356MS G++ 3.91K 2010-05-15 15:52:05 9 24880 _gXX 36740K 1370MS Pascal 5.06K 2010-05-21 20:30:14 10 24096 tracyhenry 44520K 1371MS Pascal 5.51K 2010-05-18 19:01:05 11 23341 jsn1993 11968K 1373MS G++ 3.17K 2010-05-15 07:54:22 12 24554 cly 48776K 1574MS Pascal 7.06K 2010-05-20 10:29:23 13 24512 bonism 57724K 1636MS G++ 3.76K 2010-05-20 07:57:28 14 24901 edward_mj 6652K 1638MS G++ 4.48K 2010-05-21 21:46:52 【CODE】
#include #include #include const int E=2000005;
const int N=100005;
const int px[8]={-1,-1,-1, 0, 0, 1, 1, 1};
const int py[8]={-1, 0, 1,-1, 1,-1, 0, 1};
int n,tot,cnt,Lt;
int fa[N],order[N],List[N],F[N];
bool v[N];
struct Node{int x,y,T,w,pos;}a[N];
struct edge{int x,y;edge *next;};
struct Gtp{
int e;
edge g[E],*ls[100005];
void init(){e=0; for (int i=0;i void add(int x,int y){
if (!x || !y || x==y) return;
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

void op(){
int tmp=e,i;
init();
for (i=1;i<=tmp;i++)
add(g[i].y,g[i].x);
}

void Turn_fa(){
int tmp=e,i;
init();
for (i=1;i<=tmp;i++)
add(fa[g[i].x],fa[g[i].y]);
}

void dfs(int p,bool Type){
v[p]=true;
if (Type) fa[p]=cnt;
for (edge *t=ls[p];t;t=t->next)
if (!v[t->y]) dfs(t->y,Type);
if (!Type) order[++tot]=p;
}
}G;

void input(){
int r,c,i;
scanf("%d%d%d",&n,&r,&c);
for (i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].T);
a[i].pos=i;
a[i].w=0;
fa[i]=i;
}
}

int cmpR(const void *A,const void *B){
return ((Node*)A)->x-((Node*)B)->x;
}
int cmpC(const void *A,const void *B){
return ((Node*)A)->y-((Node*)B)->y;
}
int cmpFree(const void *A,const void *B){
if (((Node*)A)->x!=((Node*)B)->x) return ((Node*)A)->x-((Node*)B)->x;
return ((Node*)A)->y-((Node*)B)->y;
}
int cmpdp(const void *A,const void *B){
return ((Node*)A)->pos-((Node*)B)->pos;
}

struct R_Function{
void deal(){
qsort(a+1,n,sizeof(Node),cmpR);
int i,j,k,st,pre;
for (i=1;i<=n;i=j+1){
for (j=i;j for (k=i,st=0,pre=0;k<=j;k++)
if (a[k].T==1){
if (!st) st=a[k].pos;
else G.add(pre,a[k].pos);
pre=a[k].pos;
}
G.add(pre,st);
for (k=i;k<=j;k++)
if (a[k].T!=1)
G.add(st,a[k].pos);
}
}
}R;

struct C_Function{
void deal(){
qsort(a+1,n,sizeof(Node),cmpC);
int i,j,k,st,pre;
for (i=1;i<=n;i=j+1){
for (j=i;j for (k=i,st=0,pre=0;k<=j;k++)
if (a[k].T==2){
if (!st) st=a[k].pos;
else G.add(pre,a[k].pos);
pre=a[k].pos;
}
G.add(pre,st);
for (k=i;k<=j;k++)
if (a[k].T!=2)
G.add(st,a[k].pos);
}
}
}C;

struct Free_Function{
int Find(int x,int y){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (a[mid].x else r=mid;
}
if (a[l].x==x && a[l].y==y) return a[l].pos;
return 0;
}

void deal(){
qsort(a+1,n,sizeof(Node),cmpFree);
int i,j;
for (i=1;i<=n;i++)
if (a[i].T==3)
for (j=0;j<8;j++)
G.add(a[i].pos,Find(a[i].x+px[j],a[i].y+py[j]));
}
}Free;

void SCC(){
G.Turn_fa();
memset(v,false,sizeof(v));
int i,j; tot=Lt=0;
for (i=1;i<=n;i++)
if (!v[i])
G.dfs(i,false);
G.op();
memset(v,false,sizeof(v));
for (j=tot;j>=1;j–){
i=order[j];
if (!v[i]){
cnt=i;
List[++Lt]=i;
G.dfs(i,true);
}
}
G.op();
G.Turn_fa();
}

void dp(){
qsort(a+1,n,sizeof(Node),cmpdp);
memset(F,0,sizeof(F));
int i,j,ans=0;
for (i=1;i<=n;i++) a[fa[i]].w++;
for (j=1;j<=Lt;j++){
i=List[j];
F[i]+=a[i].w;
for (edge *t=G.ls[i];t;t=t->next)
if (F[i]>F[t->y]) F[t->y]=F[i];
if (F[i]>ans) ans=F[i];
}
printf("%dn",ans);
}

int main(){
input();
R.deal();
C.deal();
Free.deal();
SCC();
dp();
}

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注