HauntedProgrammer's Blog

A said strange person

[BZOJ 4078][Wf2014]Metal Processing Plant

HauntedProgrammer posted @ 2015年5月24日 14:46 in 未分类 , 992 阅读

一血!!

首先枚举[tex]{threshold}_A[/tex],然后二分算出最小的[tex]{threshold}_B[/tex]。判断可行性时可以用2-SAT。

这样是[tex]O(n^4log(n))[/tex]的。注意到可能的[tex]{threshold}_A[/tex]只可能是矩阵的最大生成树中的边和对最大生成树黑白染色以后同色之间的最大权值,这样复杂度就变成[tex]O(n^3log(n))[/tex]了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
#define MAXN 410
#define MAXT 80015
struct ev{int x,y;} evs[MAXT];
int n,ai[MAXN][MAXN],map[MAXT],mc=0,p[MAXN],pos[MAXN],col[MAXN],pn=0;
int st1[MAXN],nex1[MAXT],to1[MAXT],e_num1=0;
int st2[MAXN],nex2[MAXT],to2[MAXT],e_num2=0;
int seq[MAXN],dfc,scc[MAXN],scn;
bool vis[MAXN];
inline void addedge1(int u,int v){nex1[e_num1]=st1[u],to1[e_num1]=v,st1[u]=e_num1++;}
inline void addedge2(int u,int v){nex2[e_num2]=st2[u],to2[e_num2]=v,st2[u]=e_num2++;}
inline bool cmp(const ev &lhs,const ev &rhs){return ai[lhs.x][lhs.y]>ai[rhs.x][rhs.y];}
inline int root(int x){return p[x]==x?x:p[x]=root(p[x]);}
inline int T(int x){return (x<<1);}
inline int F(int x){return (x<<1)+1;}
std::vector<int> g[MAXN];
void dfs1(int x){vis[x]=true;for(int i=st1[x];~i;i=nex1[i]) if(!vis[to1[i]]) dfs1(to1[i]);seq[dfc++]=x;}
void dfs2(int x){scc[x]=scn;for(int i=st2[x];~i;i=nex2[i]) if(!~scc[to2[i]]) dfs2(to2[i]);}
void dfs3(int x,int fa){for(int i=0,len=g[x].size();i<len;i++) if(g[x][i]!=fa) col[g[x][i]]=col[x]^1,dfs3(g[x][i],x);}
bool check(int tha,int thb)
{
	if(thb>tha) return false;
	memset(st1,-1,sizeof(st1)),memset(st2,-1,sizeof(st2)),e_num1=e_num2=0;
	memset(scc,-1,sizeof(scc)),memset(vis,0,sizeof(vis)),dfc=scn=0;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(ai[i][j]>tha) addedge1(T(i),F(j)),addedge2(F(i),T(j));
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(ai[i][j]>thb) addedge1(F(i),T(j)),addedge2(T(i),F(j));
	for(int i=0;i<(n<<1);i++) if(!vis[i]) dfs1(i);
	for(int i=dfc-1;~i;i--) if(!~scc[seq[i]]) dfs2(seq[i]),scn++;
	for(int i=0;i<n;i++) if(scc[T(i)]==scc[F(i)]) return false;
	return true;
}
int getans(int tha)
{
	if(!check(tha,tha)) return ~(0u)>>1;
	int lb=0,rb=mc,mid;
	while(map[lb]>tha) lb++;
	while(rb-lb>1)
	{
		mid=(lb+rb)>>1;
		if(check(tha,map[mid])) lb=mid;
		else rb=mid;
	}
	return tha+(check(tha,map[rb])?map[rb]:map[lb]);
}
int main()
{
	scanf("%d",&n);
	if(n<=2){printf("0\n");return 0;}
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) scanf("%d",&ai[i][j]),ai[j][i]=map[mc]=ai[i][j],evs[mc]=(ev){i,j},mc++;
	std::stable_sort(map,map+mc,std::greater<int>()),std::stable_sort(evs,evs+mc,cmp);
	for(int i=0;i<n;i++) p[i]=i;
	for(int i=0,r1,r2;i<mc;i++)
	{
		r1=root(evs[i].x),r2=root(evs[i].y);
		if(r1!=r2) p[r1]=r2,g[evs[i].x].push_back(evs[i].y),g[evs[i].y].push_back(evs[i].x),pos[pn++]=ai[evs[i].x][evs[i].y];
	}
	dfs3(0,-1);
	int maxi=0;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(!col[i]&&!col[j]) maxi=std::max(maxi,ai[i][j]);
	pos[pn++]=maxi;
	maxi=0;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(col[i]&&col[j]) maxi=std::max(maxi,ai[i][j]);
	pos[pn++]=maxi;
//	for(int i=0;i<pn;i++) printf("%d ",pos[i]);
//	printf("\n");
	int ans=~(0u)>>1;
	for(int i=0;i<pn;i++) ans=std::min(ans,getans(pos[i]));
	printf("%d\n",ans);
	return 0;
}
Avatar_small
gzz 说:
2017年4月05日 20:12

"可能的threshold_A只可能是矩阵的最大生成树中的边和对最大生成树黑白染色以后同色之间的最大权值"
这是为什么..?求指教


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter