HauntedProgrammer's Blog

A said strange person

[BZOJ 4078][Wf2014]Metal Processing Plant

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

一血!!

首先枚举[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只可能是矩阵的最大生成树中的边和对最大生成树黑白染色以后同色之间的最大权值"
这是为什么..?求指教

Avatar_small
office cleaning serv 说:
2021年9月01日 20:29

The project of baby involves handling lots connected with mess. Moms (in particular housewives) usually are mostly down the middle of messy tasks. Sometimes there're found wiping the sticky fingers along with times there're sorting as a result of mental situation. For these individuals, the basis of calmness for a short time tends for being painfully evasive. For these individuals, standard house cleaning services usually are nothing a lot less than a godsend. The moods connected with moms are observed to vary for the higher quality, once the household clean-up work wraps up.

Avatar_small
pavzi.com 说:
2023年6月08日 19:31

Pavzi Post is a startup by passionate webmasters and bloggers who have a passion to provide engaging content which is accurate, interesting and worthy to read. We are more like a web community where you can find different information, pavzi.com resources, and topics on day-to-day incidents or news. We provide you with the finest web content on each and every topic possible with help of the editorial and content team.

Avatar_small
pavzi.com 说:
2023年6月08日 19:33
Pavzi Post is a startup by passionate webmasters and bloggers who have a passion to provide engaging content which is accurate, interesting and worthy to read. We are more like a web community where you can  find different information, <a href="https://pavzi.com/">pavzi.com</a> resources, and topics on day-to-day incidents or news. We provide you with the finest web content on each and every topic possible with help of the editorial and content team.

 

 
Avatar_small
maid services dubai 说:
2024年1月30日 02:50

As well as recommended that whenever shopping all around for fat paintings having wholesale manufacturers; conduct this search in your favorite artists' label. For case, if this can be a Vincent Jeep Gogh formation that you want, then try to find these good artists is effective. Moreover, a lot more famous this artist, the more are the number of internet retailers dealing because of their works of art.


登录 *


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