图论模拟
【简述情况】:
\(110/400\)
\(20 \leq rank\)
\(AC:1\)
有思路但未\(AC:0\)
无思路\(:3\)
| \(LUOGU4304\) | 二分图最大匹配 |
| \(LUOGU1642\) | 树转序列，\(0/1\)分数规划 |
| \(BSOJ3959\) | 最小割 |
| \(LUOGU4553\) | 上下界费用流 |
【第一题】
题意：给定棋盘上一些可放置棋子位置，其中在放置棋子的日字八个位置不能放棋
思路：套路黑白染色后求最大匹配
注意：时间上：用\(Dinic\)而不能用\(Hungary\)
空间上：开\(2*n*n\)
【第二题】
题意：求：一个\(n\)点有\(v,w\)点权的树上，点数为\(n-m\)的子树中\(\frac{\sum w_i}{\sum v_i}\)最大的值
思路:看到分数最值的题应该自然想到\(0/1\)分数规划，顺便温习一下其推导过程
另设\(\frac{\sum w_i}{\sum v_i}=\lambda\)
则$\sum w_i-\lambda \ast \sum v_i=0 $
令$g(x)=max(\sum w_i-x \ast \sum v_i) $
可证明\(g(x)\)单调递减
则对当前二分值\(mid\)对\(g(mid)\)分三类
\(g(mid)>0 <=> mid<\lambda\)
\(g(mid)<0 <=> mid>\lambda\)
\(g(mid)=0 <=> mid=\lambda\)
即可二分解决
而对于确定的\(mid\)解决\(g(mid)\)被转化成了树上的资源分配问题(背包)
可以设\(dp(x,i)\)表示以\(x\)为根子树(\(x\)要取)中取\(i\)点的最大值
则\(dp(x,i)=max(dp(y,j)+dp(x,i-j))(y\mid y\)为x儿子\(,j\mid 1\leq j \leq i)\)
相同于背包\(dp\)的j要倒序枚举才正确
【第三题】
题意：给定一个边带正权的\(M\)边\(N\)点连通无向图\(G=(V,E)\)，加入一条边\((u->v)\)边权为\(l\)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
思路：先举最小生成树的例子：考虑最小生成树上链接两个联通块间的最短边
因此，如果加入\((u->v)\)这条边连接\(u\)所在集合\(U\)与\(v\)所在集合\(V\)的边一定小于等于\(l\)不然就违背最小生成树定义，因此需要删去的边是权值\(<l\)并连接\(U\) \(V\)两个联通块的边，令其最小即是\(U\) \(V\)间最小割定义
最大生成树亦然，只需选出权值\(>l\)并连接\(U\) \(V\)两个联通块的边
步骤：
1.选出权值\(<l\)并连接\(U\) \(V\)两个联通块的边，求\(s=u->t=v\)最小割
2.选出权值\(>l\)并连接\(U\) \(V\)两个联通块的边，求\(s=u->t=v\)最小割
【第四题】
题意：过于复杂，查看原题
思路：这道题我们考虑上下界费用流建模。
首先将每个点拆成\(a_i\)和\(a_i'\),分别用来限制入度\((\leq m)\)出度\((=v_i)\)
超级源点向\(a_i\)连一条容量为\(v_i\)，费用为\(0\)的边；
\(a_i'\)向超级汇点连一条容量为\(v_i\)，费用为\(0\)的边；
源点向\(a_i\)连一条容量为\(INF\)，费用为\(0\)的边；
\(a_i'\)向汇点连一条容量为\(INF\)，费用为0的边。
对于原图一条\(x->y\)，费用为\(w\)的边：
\(x'\)向\(y\)连一条容量为\(INF\)，费用为\(w\)的边。
【小结】
这次考了\(3\)道网络流题，\(1\)道\(0/1\)分数规划问题
说明两个问题:
1.知识掌握不够熟练 ： \(0/1\)分数规划问题讨论思路
2.思路不够宽 : 最小割转化思想
对过去知识要灵活运用，不要局限套路做法，分析题目本质，步步踏实才是王道
【推进练习】
上下界费用流：\(BSOJ5313\)
\(T4\)类似建图:\(BSOJ3303\)
\(0/1\)分数规划两题:
\(0/1\)分数规划+背包 \(LUOGU4377\)
\(0/1\)分数规划+树上背包 最佳团体\(LUOGU4322\)