首页 > 代码库 > BZOJ4684 : Company Organization
BZOJ4684 : Company Organization
二分答案，转化为判定问题。
建立有向图，$a->b$连边表示$a$是$b$的子集，至此可以处理掉$1$和$2$。
对于$5$，则往对应点的集合塞一个元素，即可满足$5$。
首先求出强连通分量进行缩点，再递推出每个集合的必备元素以及每个集合的所有子集，用bitset加速，可以做到$O(\frac{m^2}{32})$。
然后对于$4$，首先检验一下$5$造成的必备元素是否有交，然后将所有既能到$x$又能到$y$的集合都标记为空集，这一步同样可以用bitset加速，做到$O(\frac{nm}{32})$。
知道哪些集合必须是空集之后，再检查是否存在一个集合，满足它必须是空集但是却又有操作$5$的元素。
最后再检查$3$即可，如果$x$和$y$所属同一个强连通分量或两个都是空集则矛盾。
时间复杂度$O(\frac{m^2\log m}{32})$。
#include<cstdio>const int N=105,M=10005,E=M*2;int n,m,U,i,j,x,y,e[M][3],l,r,mid,ans;int g[3][N],v[3][E],nxt[3][E],ed;int d[N],vis[N],h,t,q[N],f[N],empty[N];struct BIT{ unsigned int v[M>>5]; BIT(){} void clear(){for(int i=0;i<=U;i++)v[i]=0;} void set(int x){v[x>>5]^=1U<<(x&31);} void operator|=(const BIT&b){for(int i=0;i<=U;i++)v[i]|=b.v[i];} bool operator&(const BIT&b){for(int i=0;i<=U;i++)if(v[i]&b.v[i])return 1;return 0;} void pick(const BIT&b,const BIT&w){ for(int i=t=0;i<=U;i++){ unsigned int x=v[i]&b.v[i]&w.v[i]; while(x){ q[++t]=i<<5|__builtin_ctz(x&-x); x-=x&-x; } } }}s[N],sub[N],w;inline void add(int x,int y){ v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed; v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed;}inline void ADD(int x,int y){d[y]++;v[2][++ed]=y;nxt[2][ed]=g[2][x];g[2][x]=ed;}void dfs1(int x){ vis[x]=1; for(int i=g[0][x];i;i=nxt[0][i])if(!vis[v[0][i]])dfs1(v[0][i]); q[++t]=x;}void dfs2(int x,int y){ vis[x]=0,f[x]=y,s[y]|=s[x],sub[y]|=sub[x]; for(int i=g[1][x];i;i=nxt[1][i])if(vis[v[1][i]])dfs2(v[1][i],y);}bool check(int mid){ for(U=0,i=1;i<=mid;i++)if(e[i][0]==5)U++; if(U<n)U=n; U=(U-1)>>5; w.clear(); for(ed=0,i=1;i<=n;i++){ g[0][i]=g[1][i]=g[2][i]=d[i]=empty[i]=0; s[i].clear(); sub[i].clear(); sub[i].set(i-1); w.set(i-1); } for(t=0,i=1;i<=mid;i++){ x=e[i][1],y=e[i][2]; if(e[i][0]==1)add(x,y); if(e[i][0]==2)add(x,y),add(y,x); if(e[i][0]==5)s[x].set(t),s[y].set(t++); } for(t=0,i=1;i<=n;i++)if(!vis[i])dfs1(i); for(i=n;i;i--)if(vis[q[i]])dfs2(q[i],q[i]); for(ed=0,i=1;i<=n;i++)for(j=g[0][i];j;j=nxt[0][j])if(f[i]!=f[v[0][j]])ADD(f[i],f[v[0][j]]); for(t=0,h=i=1;i<=n;i++)if(f[i]==i&&!d[i])q[++t]=i; while(h<=t)for(i=g[2][x=q[h++]];i;i=nxt[2][i]){ s[v[2][i]]|=s[x]; sub[v[2][i]]|=sub[x]; if(!(--d[v[2][i]]))q[++t]=v[2][i]; } for(i=1;i<=mid;i++)if(e[i][0]==4){ x=f[e[i][1]],y=f[e[i][2]]; if(s[x]&s[y])return 0; for(sub[x].pick(sub[y],w);t;t--)empty[q[t]+1]=1,w.set(q[t]); } for(i=1;i<=n;i++)if(f[i]==i)if((s[i]&s[i])&&empty[i])return 0; for(i=1;i<=mid;i++)if(e[i][0]==3){ x=f[e[i][1]],y=f[e[i][2]]; if(x==y)return 0; if(empty[x]&&empty[y])return 0; } return 1;}int main(){ while(1){ scanf("%d%d",&n,&m); if(!n)return 0; for(i=1;i<=m;i++)scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); l=1,r=m,ans=0; while(l<=r)if(check(mid=(l+r)>>1))l=(ans=mid)+1;else r=mid-1; printf("%d\n",ans); }}
BZOJ4684 : Company Organization
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。