luoguP3355 骑士共存问题

原题传送门>Here<

我们首先观察发现,可以将图中的点分成奇数点和偶数点。也就是说,对于点(x,y),依据(x+y)的奇偶性分成两个点集。这样可以保证每个点所能攻击到的点一定和它在不同的集合中。

1.从源点到每个没有障碍的奇数点建1条流为1的边;

2.从每个没有障碍的奇数点到其可以攻击且没有障碍的偶数点建1条流为inf的边;

3.从每个没有障碍的偶数点到汇点建1条流为1的边。

这样建图以后,每一条从源点到汇点的弧表示有两个点会相互攻击。计算出图的最小割ans,即 使源点到汇点不连通所要花费的最小代价,它的实际意义就是在所有没有障碍的点中至少需要删除多少个才能使得没有点可以相互攻击。

于是答案就是n*n-m-ans.

又因为最小割=最大流,所以建图后跑一边dinic即可。

luoguP3254 圆桌问题

原题传送门>Here<

我果然还是太蒟了。。。这道题都调了两三次才过。

网络流建图:

1.因为每个单位只能有r[i]位代表,所以从源点到每个单位建流为r[i]的边;

2.同一单位代表不能同桌就餐->每桌每单位最多只有一位代表

于是从每个单位到每桌建流为1的边;

3.从每桌到汇点建流为c[i]的边。

这样最大流就是最多可分配的代表人数,如果<总人数则无解

跑完dinic后枚举2中的道路查看流的大小是否为0,为0则表示被选,输出即可。

dinic bfs时必须写h<t!dinic bfs时必须写h<t!dinic bfs时必须写h<t!

(因为写成h<=tTLE了很多次)

luoguP2774 方格取数问题

原题传送门>Here<

这道题和骑士共存问题基本没差。

在这道题里,我们只要把边权从1改到$num[i][j]$就可以水过了。

luoguP2763 试题库问题

原题传送门>Here<

网络流水题。考虑每种题目数量为定值,且每道题只能对应一种题型,用二分图的方法建图:

1:从源点到每道题目连一条流为1的边;

2:从每道题目到其属于的题型建流为1的边;

3:从每种题型到汇点建流为(要求数量)的边。

然后跑一遍网络流就过了。

luoguP3224 [HNOI2012]永无乡

原题传送门 >Here<

平衡树+启发式合并。

建桥就相当于合并两棵平衡树,查询时查找树中第K小就可以了。

于是只剩下如何合并两棵平衡树的问题了。话说这道题真的很玄学,我本来以为有一种不明觉厉的方法可以迅速整体合并两棵平衡树,但是想了很久也没有想出来。看了各位dalao的博客才发现原来可以暴力把一棵平衡树的点全部拆出来插入到另一棵树上,并且每次合并两棵树时选取节点数少的树拆,据说这样可以保证每个点最多更新logn次(也就是启发式合并)。

然后就可以过了。。。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×