专栏文章

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

PPizzaYY
P6898题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mincecen
此快照首次捕获于
2025/12/02 00:07
3 个月前
此快照最后确认于
2025/12/02 00:07
3 个月前
查看原文

思路

神仙题。
钦定 d(A)>d(B)d(A)>d(B)，枚举 d(A)d(A)，二分 d(B)d(B) 的最小取值，判定可以使用 2-sat。时间复杂度 O(n4log⁡n2)O(n^4\log n^2)。
考虑优化，可以从大到小枚举最大的边，并把这条边加入一个新图中。我们发现，在当前情况中，最大边的两个端点一定在同一个集合中，其他边的端点不在同一个集合中。
分下面几种情况：
  1. 加入后形成一个环：
    • 若为奇环，继续枚举下去，奇环上相邻两点颜色不同，一定不存在一种合法的染色方案，所以可以算完当前最大值的答案后退出枚举；
    • 若为偶环，当前需要两端点相同，把两个端点缩起来后就变成奇环了，一定不存在合法的染色方案，则枚举下一个最大边。
  2. 加入后不形成环：这样的边最多只有 O(n)O(n) 个，可以暴力。
最后发现需要计算的最大边只有 O(n)O(n) 个，对于每个最大边二分即可做到 O(n3log⁡n)O(n^3\log n)。注意特判答案为零的情况。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int n,f[N<<1],cnt;
inline int find(int x)
{
	if(f[x]==x) return x;
	return f[x] = find(f[x]);
}
struct node{
	int u,v,w;
	inline friend bool operator < (node x,node y)
	{
		return x.w>y.w;
	}
}e[N*N];
vector<int> g[N<<1];
int dfn[N<<1],low[N<<1],idx,stk[N<<1],top,scc[N<<1],c;
bool inc[N<<1];
void dfs(int u)
{
	dfn[u] = low[u] = ++idx,stk[++top] = u,inc[u] = 1;
	for(auto v:g[u])
	{
		if(!dfn[v])
		{
			dfs(v);
			low[u] = min(low[u],low[v]);
		}
		else if(inc[v]) low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		c++;
		while(stk[top]!=u)
			inc[stk[top]] = 0,scc[stk[top]] = c,top--;
		inc[u] = 0,scc[u] = c,top--;
	}
}
inline bool ok(int x,int y)
{
	for(int i = 1;i<=2*n;i++)
		g[i].clear(),dfn[i] = low[i] = inc[i] = scc[i] = 0;
	idx = top = c = 0;
	for(int i = 1;i<=cnt;i++)
	{
		int u = e[i].u,v = e[i].v;
		if(e[i].w>x)
		{
			g[u].push_back(v+n),g[v].push_back(u+n);
			g[v+n].push_back(u),g[u+n].push_back(v);
		}
		else if(e[i].w>y)
		{
			g[u].push_back(v+n),g[v].push_back(u+n); 
		}
	}
	for(int i = 1;i<=2*n;i++) if(!dfn[i]) dfs(i);
	for(int i = 1;i<=n;i++)
		if(scc[i]==scc[i+n]) return 0;
	return 1;
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
		for(int j = i+1;j<=n;j++)
			cnt++,e[cnt].u = i,e[cnt].v = j,cin>>e[cnt].w;
	sort(e+1,e+cnt+1);
	int ans = 2e9;
	for(int i = 1;i<=2*n;i++) f[i] = i;
	for(int i = 1;i<=cnt;i++)
	{
		int u = e[i].u,v = e[i].v,w = e[i].w;
		if(find(u)==find(v+n)) continue;
		f[find(u)] = find(v+n),f[find(v)] = find(u+n);
		int l = i,r = cnt+1,res = -1;
		while(l<=r)
		{
			int mid = (l+r)/2;
			if(ok(w,e[mid].w)) res = mid,l = mid+1;
			else r = mid-1;
		}
		if(res!=-1) ans = min(ans,e[res].w+w);
		if(find(u)==find(u+n)) break;
	}
	if(ok(0,0)) ans = 0;
	cout<<ans<<'\n';
	return 0;
}

评论

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

正在加载评论...