BJ-图论网络流

A.qoj 9904

瓶颈在于很多区间重复合并，考虑把区间挂到 ST 表上，每次要连的一定是 l,r 往后走的一段区间。

所以可以判断是否相连，如果没有，就递归下去找直到相邻或只有一个点，然后把两段区间连上。

点击查看代码

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,a[N*2],id[N*2],f[N][22];
bool cmp(int x,int y)
{
	return a[x]<a[y];
}
int find(int x,int k)
{
	if(f[x][k]!=x) f[x][k]=find(f[x][k],k);
	return f[x][k];
}
int cnt=0;
void solve(int x,int y,int k)
{
	int u=find(f[x][k],k),v=find(f[y][k],k);
	if(u==v) return ;
	if(k==0)
	{
		f[u][k]=v,cnt++;
		return;
	}
	int p=(1<<(k-1));
	solve(x,y+p,k-1);
	solve(x+p,y,k-1);
	f[u][k]=v;
}
int merge(int x,int y,int len)
{
	cnt=0;
	for(int i=20;i>=0;i--)
	{
		if(!((len>>i)&1)) continue;
		int p=(1<<i);
//		printf("%d %d %d %d\n",i,x,y,len);
		solve(x,y-p+1,i);
		y-=p,x+=p;
	}
//	printf("a");
	return cnt;
}
int main()
{
	scanf("%d",&n);
	for(int i=3;i<=2*n-1;i++)
	{
		scanf("%d",&a[i]);
		id[i]=i;
	}
	sort(id+3,id+2*n,cmp);
	for(int j=0;j<=20;j++)
	{
		for(int i=1;i<=n;i++) f[i][j]=i;
	}
//	printf("a");
	ll ans=0;
	for(int t=3;t<=2*n-1;t++)
	{
		int i=id[t];
		int x=i/2,len;
//		printf("%d ",i);
		if(i%2==0)
		{
			len=min(x-1,n-x);
			ans+=1ll*a[i]*merge(x-len,x+len,len); 
		}
		else
		{
			len=min(x,n-x);
//			printf("%d %d\n",len,x);
			ans+=1ll*a[i]*merge(x-len+1,x+len,len);
		}
	}
	printf("%lld",ans);
	return 0;
}

B.qoj 14718

这个可以转化为最早什么时候能让两个点相遇，看每个人在哪里和其他人相遇。

对于任意一个相遇点，一定是找最近的点产生贡献，把这些点丢进去跑全源最短路。

不会了。

C.qoj 4218

所有导出子图都存在一个点度数 \(\le k\) 的点可以 k+1 染色。

然后每次新加入一个点，就对每个独立集询问是否存在边，若存在，就把这个点删去再继续问。

D.Hidden Bipartite Graph

可以先弄出来一棵树，因为树是二分图，所以可以直接划分左右部点，然后询问这两部分是否有边即可。

判断一个点到一个集合是否有边，先询问集合再带上这个点，做差即可。

具体询问集合的时候，可以用一个类似二分的方法。

找到一个点就递归下去，如果到了叶子就直接返回，同时标记每个已经在树上的点，不再询问。

询问复杂度就是遍历树的次数乘上二分的次数，大概是 \(O(n\log n)\)，带个 2 倍常数。

E.Case of Computer Network

显然边双可以直接定向成环，这样就随便走了。

接下来考虑割边，显然只能有一个方向，此时缩点后一定是一个森林。

然后做一个树上差分，如果一条边既有上标记又有下标记，那么一定没解。

F.「SWTR-8」地地铁铁

先考虑不再一个点双内，唯一不合法的情况就是经过的点双全部同色。

因为如果既有 d 又有 D，那么一定可以走到两种颜色。

不会了。

G.Cycle sort

假设互不相同，令 \(b=sort(a)\)，从 \(a_i\) 向 \(b_i\) 连边。

最简单的，环个数次一定可以完成并且代价最小，就是不再位置上的数个数。

当限制不太严的情况下，可以把环串起来，会有环个数个元素位置不对，并且构成环，一共转 2 次。

当限制加紧的情况，可以发现环个数，减少串在一起的环个数就可以了。

考虑更一般的情况，可以发现是一些欧拉回路，不会了。

H.Dining G

网络流板子，看作食物和饮料匹配，牛就相当于其中的连边。

但是每只奶牛只能吃一份，所以把奶牛拆点流量限制为 1。

I.最长不下降子序列问题

可以根据 dp 数组建图。

考虑最简单的 \(n^2\)，如果一个数位置在 x 的前面且值比他小，那么 \(f_x=max(f_x,f_i+1)\)。

然后从长度为 s 的点连向汇点，并且将恰好满足 \(f_x=f_i+1\) 的 \((x,i)\) 连边。

注意不能重复用的数要拆点限制流量。

J.Asteroids G

原，行列连边，最小点覆盖。

K.Making It Bipartite

不存在 3 个数满足 \(x|y|z\)

设 \(x_0\) 表示选 x 的因数，\(x_1\) 表示选倍数，显然两个不能同时选。

假设 \(x|y\)，只有 \((x_1,y_0)\) 能同时选，然后求最长反链。

L.Construction of a tree

从一号点出发，然后不断去匹配