4229: 选择

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 67  Solved: 41

Description

现在，我想知道自己是否还有选择。

给定n个点m条边的无向图以及顺序发生的q个事件。

每个事件都属于下面两种之一：

1、删除某一条图上仍存在的边

2、询问是否存在两条边不相交的路径可以从点u出发到点v

Input

第一行三个整数n,m,q

接下来m行，每行两个整数u,v，表示u和v之间有一条边

接下来q行，每行一个大写字母o和2个整数u、v，依次表示按顺序发生的q个事件：

当o为’Z’时，表示删除一条u和v之间的边

当o为’P’时，表示询问是否存在两条边不相交的路径可以从点u出发到点v

Output

对于每组询问，如果存在，输出Yes,否则输出No

Sample Input

7 8 7

1 2

1 3

1 4

2 3

3 4

3 7

7 4

5 6

Z 1 4

P 1 3

P 2 4

Z 1 3

P 1 3

Z 6 5

P 5 6

Sample Output

Yes

Yes

No

No

HINT

对于全部数据，max(n,m,q)<=100000

Source

 

 

【分析】

　　我的做法跟BZOJ 1969大致一样【我改了改代码交的。。

　　这题没说删完的图联通，所以最后还要处理一下。。

　　然后每次询问x到y的关键边数量是否为0就好了。

　　【详细做法见

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 #define Maxn 100010  8 #define Maxm 100010  9  10 struct node 11 { 12     int x,y,next; 13     int bj,id; 14 }t[Maxn*2],tt[Maxm*4]; 15 int first[Maxn],len; 16  17 void ins(int x,int y) 18 { 19     // printf("%d -> %d\n",x,y); 20     t[++len].x=x;t[len].y=y; 21     t[len].next=first[x];first[x]=len; 22 } 23  24 struct nnode 25 { 26     int l,r,lc,rc,sm; 27 }tr[Maxn*2]; 28  29 void upd(int x) 30 { 31     if(tr[x].l==tr[x].r||tr[x].sm!=0) return; 32     int lc=tr[x].lc,rc=tr[x].rc; 33     tr[lc].sm=tr[rc].sm=0; 34 } 35  36 int tot; 37 int build(int l,int r) 38 { 39     int x=++tot; 40     tr[x].l=l;tr[x].r=r; 41     if(l!=r) 42     { 43         int mid=(l+r)>>1; 44         tr[x].lc=build(l,mid); 45         tr[x].rc=build(mid+1,r); 46     } 47     else tr[x].lc=tr[x].rc=0; 48     tr[x].sm=r-l+1; 49     return x; 50 } 51  52 void change(int x,int l,int r) 53 { 54     if(tr[x].l==l&&tr[x].r==r) 55     { 56         tr[x].sm=0; 57         return; 58     } 59     upd(x); 60     int mid=(tr[x].l+tr[x].r)>>1,lc=tr[x].lc,rc=tr[x].rc; 61     if(r<=mid) change(lc,l,r); 62     else if(l>mid) change(rc,l,r); 63     else 64     { 65         change(lc,l,mid); 66         change(rc,mid+1,r); 67     } 68     tr[x].sm=tr[lc].sm+tr[rc].sm; 69 } 70  71 int query(int x,int l,int r) 72 { 73     if(tr[x].sm==0) return 0; 74     if(tr[x].l==l&&tr[x].r==r) return tr[x].sm; 75     upd(x); 76     int mid=(tr[x].l+tr[x].r)>>1,lc=tr[x].lc,rc=tr[x].rc; 77     if(r<=mid) return query(lc,l,r); 78     else if(l>mid) return query(rc,l,r); 79     else return query(lc,l,mid)+query(rc,mid+1,r); 80 } 81  82 int tp[Maxn],sum[Maxn],son[Maxn],dfn[Maxn],dep[Maxn]; 83 int ff[Maxn]; 84 int cnt; 85 void dfs(int x,int f) 86 { 87     son[x]=0;sum[x]=1;dep[x]=dep[f]+1; 88     ff[x]=f; 89     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f) 90     { 91         int y=t[i].y; 92         dfs(y,x); 93         sum[x]+=sum[y]; 94         if(son[x]==0||sum[son[x]]
           
            dfn[x]) while(1);134 ans+=query(1,dfn[y]+1,dfn[x]);135 }136 return ans;137 }138 139 int fa[Maxn];140 int ffa(int x)141 {142 if(fa[x]!=x) fa[x]=ffa(fa[x]);143 return fa[x];144 }145 146 bool cmp(node x,node y)147 {148 if(x.x==y.x&&x.y==y.y) return x.bj
            
             tt[ll].y) swap(tt[ll].x,tt[ll].y);168 tt[ll].bj=1;//cha ru169 }170 int ct=0;171 while(q--)172 {173 scanf("%s",s);174 ll++;175 scanf("%d%d",&tt[ll].x,&tt[ll].y);176 if(tt[ll].x>tt[ll].y) swap(tt[ll].x,tt[ll].y);177 if(s[0]=='Z') tt[ll].bj=-1;//shan chu178 else tt[ll].bj=0;//xun wen179 tt[ll].id=++ct;180 }181 sort(tt+1,tt+1+ll,cmp);182 for(int i=1;i<=n;i++) fa[i]=i;183 ct++;184 int pp=0;185 for(int i=1;i<=ll;i++)186 {187 if(tt[i].bj==0) continue;188 if(tt[i].bj==1)189 {190 if(pp==0||tt[i].x!=tt[pp].x||tt[i].y!=tt[pp].y)191 {192 if(ffa(tt[i].x)==ffa(tt[i].y))193 {194 tt[i].bj=-1;195 tt[i].id=ct;196 }197 else198 {199 ins(tt[i].x,tt[i].y);200 ins(tt[i].y,tt[i].x);201 fa[ffa(tt[i].x)]=tt[i].y;202 }203 }204 }205 pp=i;206 }207 sort(tt+1,tt+1+ll,cmp2);208 for(int i=ll;i>=1;i--) if(tt[i].bj==-1)209 {210 if(ffa(tt[i].x)!=ffa(tt[i].y))211 {212 ins(tt[i].x,tt[i].y);213 ins(tt[i].y,tt[i].x);214 fa[ffa(tt[i].x)]=tt[i].y;215 tt[i].bj=1;216 }217 }218 dep[0]=0;cnt=0;219 for(int i=1;i<=n;i++) if(ffa(i)==i)220 {221 dfs(i,0);222 dfs2(i,i);223 }224 build(1,n);225 226 ans[0]=0;227 for(int i=ll;i>=1;i--)228 {229 if(tt[i].bj==1) continue;230 if(tt[i].bj==-1)231 {232 fchange(tt[i].x,tt[i].y);233 }234 else235 {236 if(ffa(tt[i].x)!=ffa(tt[i].y)) ans[++ans[0]]=-1;237 else ans[++ans[0]]=fquery(tt[i].x,tt[i].y);238 }239 }240 for(int i=ans[0];i>=1;i--)241 {242 if(ans[i]==0) printf("Yes\n");243 else printf("No\n");244 }245 }246 247 int main()248 {249 solve();250 return 0;251 }
            
           
          
         
        
       
      

【是不是打的有点丑

 

2017-03-27 10:33:13