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

×