首页 > 代码库 > BZOJ4643 : 卡常大水题
BZOJ4643 : 卡常大水题
将边按权值$A$从小到大排序，从小到大枚举$\max(A)$，然后双指针从大到小枚举$\max(B)$。
按权值$B$用大根堆维护所有已经加入的边，每次$\max(B)$减少时，不断取出权值$B$最大的边看看是否需要删除即可。
那么只需要检验这个图是否只有一个强连通分量。
考虑使用Kosaraju算法，维护一个未走过的点的集合，每次与出边表取交之后递归搜索可行后继点。
这显然可以用bitset来并行计算，时间复杂度单次$O(\frac{n^2}{32})$。
总时间复杂度$O(\frac{n^4}{32}+n^2\log n)$。
#include<cstdio>#include<algorithm>#include<queue>#define N 155using namespace std;typedef unsigned int U;typedef pair<int,int>P;typedef pair<int,P>PI;int n,i,j,k,m,b[N][N],eb[N*N],q[N],t,ans=~0U>>1;priority_queue<PI>Q;struct E{int x,y,w;E(){}E(int _x,int _y,int _w){x=_x,y=_y,w=_w;}}ea[N*N];inline bool cmp(const E&a,const E&b){return a.w<b.w;}struct BIT{ U v[5]; void flip(int x){v[x>>5]^=1U<<(x&31);} int get(int x){return v[x>>5]>>(x&31)&1;}}g0[N],g1[N],v;inline void addedge(int x,int y){ if(x==y||b[x][y]>eb[j])return; Q.push(PI(b[x][y],P(x,y))); g0[x].flip(y); g1[y].flip(x);}inline void deledge(int x,int y){ g0[x].flip(y); g1[y].flip(x);}void dfs1(int x){ v.flip(x); for(int i=0;i<5;i++)while(1){ U o=v.v[i]&g0[x].v[i]; if(!o)break; dfs1(i<<5|__builtin_ctz(o)); } q[++t]=x;}void dfs2(int x){ v.flip(x); for(int i=0;i<5;i++)while(1){ U o=v.v[i]&g1[x].v[i]; if(!o)break; dfs2(i<<5|__builtin_ctz(o)); }}inline bool check(){ int i; for(i=0;i<5;i++)v.v[i]=0; for(i=0;i<n;i++)v.flip(i); for(t=i=0;i<n;i++)if(v.get(i))dfs1(i); for(i=0;i<n;i++)v.flip(i); dfs2(q[t]); for(i=0;i<5;i++)if(v.v[i])return 0; return 1;}void solve(){ sort(ea+1,ea+m+1,cmp); sort(eb+1,eb+m+1); for(i=1,j=m;i<=m;i++){ addedge(ea[i].x,ea[i].y); while(check()){ ans=min(ans,ea[i].w+eb[j]); if(!(--j))return; while(!Q.empty()){ PI t=Q.top(); if(t.first<=eb[j])break; Q.pop(); deledge(t.second.first,t.second.second); } } }}int main(){ scanf("%d",&n); for(m=i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&k),ea[++m]=E(i,j,k); for(m=i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&b[i][j]),eb[++m]=b[i][j]; solve(); return printf("%d",ans),0;}
BZOJ4643 : 卡常大水题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。