专栏文章

题解：P6898 [ICPC 2014 WF] Metal Processing Plant

PPurslaneM2GA
P6898题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mintmp6a
此快照首次捕获于
2025/12/02 08:09
3 个月前
此快照最后确认于
2025/12/02 08:09
3 个月前
查看原文
思路 1：暴力枚举 D(A)D(A) 和 D(B)D(B)，转化为 2-SAT 问题后判断是否合法，复杂度 O(n6)O(n^6)。
思路 2：在枚举 D(A)D(A) 的过程中，不用枚举 D(B)D(B) 而是对 D(B)D(B) 二分答案，复杂度 O(n4log⁡n)O(n^4 \log n)。
思路 3：在减小 D(A)D(A) 的过程中，为了保持有解 D(B)D(B) 应当增大，因此使用双指针即可做到 O(n4)O(n^4)。
思路 4：容易发现，在思路 3 中 2-SAT 建图后的边变化很少，我们使用 Kosaraju 算法就可以做到单次 O(n2w)O(\frac{n^2}{w}) 判断一组 (D(A),D(B))(D(A),D(B)) 是否合法，总复杂度 O(n4w)O(\frac{n^4}{w}) 已经能通过这道题。
思路 5：不妨设 D(A)≥D(B)D(A) \ge D(B)。建立一张新的图 GG，如果 w(i,j)>D(A)w(i,j) > D(A) 就在 (i,j)(i,j) 间连一条边。如果 (A,B)(A,B) 存在解，相当于可以将 GG 的顶点划分为两个独立集，即可以黑白二染色（是二分图）。如果不是二分图，一定无解；而如果新加的边并不会减少连通块个数（新加的边指的是，从大到小扫描 D(A)D(A) 的过程中，D(A)D(A) 在减少则 GG 中的边在增加），那么加上这条边肯定不会使 D(B)D(B) 的最小值变化（由于不存在偶环，那么新加的边的两个端点一定会出现在最优解的同一个集合中，也就是没有任何影响）。因此，可能的 D(A)D(A) 出现在“加入奇环”或者“合并两个连通分量”之前，只有 O(n)O(n) 种。然后对 D(B)D(B) 做二分答案，利用二分位置的移动量是 O(n2)O(n^2) 即可做到 O(n3+n3log⁡nw)O(n^3 + \frac{n^3 \log n}{w})。
思路 6：你要进行 O(nlog⁡n)O(n \log n) 次 2-SAT 操作，能不能再砍一些啊？感谢 @Forest114514 的题解，我们可以整体二分。即，使用整体二分确定所有 nn 个 D(A)D(A) 对应的 D(B)D(B) 的最小值，内部进行二分。当然我不会证复杂度，通过打表发现只需要进行 O(n)O(n) 次 2-SAT 操作。考虑 (D(A),D(B))(D(A),D(B)) 组的变化。首先我们对 D(A)D(A) 这一维做整体二分，移动距离为 O(n2log⁡n)O(n^2 \log n)；对 D(B)D(B) 内层做了若干次二分，总的移动距离也为 O(n2log⁡n)O(n^2 \log n)（每一次二分，D(B)D(B) 的移动距离是 D(B)D(B) 可行区间的长度，每一层这个值为 O(n2)O(n^2)；D(A)D(A) 的移动距离随便用主定理分析一下，发现也是 O(n2log⁡n)O(n^2 \log n)）。总复杂度为 O(n2log⁡n+n3w)O(n^2 \log n + \frac{n^3}{w})，非常厉害。
代码：
CPP
#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=400+10;
int n,dis[MAXN][MAXN],lsh[MAXN*MAXN],m,mx[MAXN];
bitset<MAXN> G[MAXN],g[MAXN];

//====2-SAT====
int col[MAXN],cs,tot,idx[MAXN];
bitset<MAXN> vis;
void dfs1(int u) {
	vis[u]=0;
	while(1) {
		int to=(vis&G[u])._Find_first();
		if(to>=1&&to<=n+n) dfs1(to);
		else break ;
	}
	idx[++tot]=u;
	return ;	
}
void dfs2(int u,int c) {
	vis[u]=0,col[u]=c;
	while(1) {
		int to=(vis&g[u])._Find_first();
		if(to>=1&&to<=n+n) dfs2(to,c);
		else break ;
	}
	return ;
}
void Kosaraju(void) {
	ffor(i,1,n+n) vis[i]=1;
	tot=cs=0;
	ffor(i,1,n+n) if(vis[i]) dfs1(i);
	ffor(i,1,n+n) vis[i]=1;
	roff(i,n+n,1) if(vis[idx[i]]) ++cs,dfs2(idx[i],cs);
	return ;
}
//====2-SAT====

vector<pair<int,int>> occ[MAXN*MAXN];
int tA,tB;
int check(int A,int B) {
	while(tA>A) {
		for(auto pr:occ[tA]) {
			int u=pr.first,v=pr.second;
			G[u][v+n]=G[v][u+n]=g[v+n][u]=g[u+n][v]=1;
		}
		--tA;
	}
	while(tB>B) {
		for(auto pr:occ[tB]) {
			int u=pr.first,v=pr.second;
			G[u+n][v]=G[v+n][u]=g[v][u+n]=g[u][v+n]=1;	
		}
		--tB;
	}
	while(tA<A) {
		++tA;
		for(auto pr:occ[tA]) {
			int u=pr.first,v=pr.second;
			G[u][v+n]=G[v][u+n]=g[v+n][u]=g[u+n][v]=0;
		}
	}
	while(tB<B) {
		++tB;
		for(auto pr:occ[tB]) {
			int u=pr.first,v=pr.second;
			G[u+n][v]=G[v+n][u]=g[v][u+n]=g[u][v+n]=0;	
		}
	}
	Kosaraju();
	ffor(i,1,n) if(col[i]==col[i+n]) return 0;
	return 1;
}

int ans,cnt,cA[MAXN],fa[MAXN];
int find(int k) {return (fa[k]==k)?k:(fa[k]=find(fa[k]));}
void solve(int l,int r,int bl,int br) {
	if(l>r) return ;
	if(bl==br) return ans=min(lsh[cA[l]]+lsh[bl],ans),void();
	int p=cA[(l+r>>1)],tans=br,L=bl,R=br-1;
	while(L<=R) {
		int mid=(L+R>>1);
		if(check(p,mid)) tans=mid,R=mid-1;
		else L=mid+1;
	}
	ans=min(ans,lsh[p]+lsh[tans]);
	solve(l,(l+r>>1)-1,tans,br);
	solve((l+r>>1)+1,r,bl,tans);
	return ;
}

int FA[MAXN];
int FIND(int k) {return (FA[k]==k)?k:(FA[k]=FIND(FA[k]));}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n) ffor(j,i+1,n) cin>>dis[i][j],dis[j][i]=dis[i][j],lsh[++m]=dis[i][j];
	lsh[++m]=0;
	sort(lsh+1,lsh+m+1),m=unique(lsh+1,lsh+m+1)-lsh-1;
	ffor(i,1,n) ffor(j,i+1,n) dis[i][j]=dis[j][i]=lower_bound(lsh+1,lsh+m+1,dis[i][j])-lsh,occ[dis[i][j]].push_back({i,j});
	ans=lsh[m];
	ffor(i,1,n) fa[i]=i,FA[i]=i,FA[i+n]=i+n;
	
	int ts=0;
	roff(i,m,1) {
		int flg=0;
		for(auto pr:occ[i]) {
			int u=pr.first,v=pr.second;
			if(find(u)!=find(v)) flg=1,fa[find(u)]=find(v);
			
			FA[FIND(u)]=FIND(v+n),FA[FIND(v)]=FIND(u+n);
			
			if(FIND(u)==FIND(u+n)||FIND(v)==FIND(v+n)) ts=1;
		}
		
		if(ts) {cA[++cnt]=i;break ;}
		if(flg||i==1) cA[++cnt]=i;
	}
	
	ffor(i,1,n) fa[i]=i;
	
	reverse(cA+1,cA+cnt+1);
	tA=tB=m;
	solve(1,cnt,1,m);
	cout<<ans;
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...