辞旧迎新之际,喜羊羊正在打理羊村的绿化带,然后他发现了一棵长着毒瘤的树。

这个长着毒瘤的树可以用 $n$ 个结点 $m$ 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点,即删掉这个结点和与之相邻的边之后,这个图会变为一棵树。树也即无简单环的无向连通图。

现在给你这个无向图,喜羊羊请你帮他求出所有毒瘤结点。

C++读入优化的黑科技

输出优化

除了读入的黑科技以外,输出也有黑科技。
和fread对应,输出黑科技叫fwrite,就是把一整个字符串(快速地)写进输出文件。
也就是说在输出的时候,把输出的内容存进字符串,再用fwrite输出会很快(实验结果待填)

模板-缩点

传送门
把强连通分量缩成一个点,然后对DAG跑拓扑排序,处理出最大值。
其实是【模板】缩点+【模板】拓扑排序

模板--高斯消元

原题传送门
$A×X=B$,已知矩阵$A$,$B$,求矩阵$X$。
算法流程:

  1. 把A消成上三角矩阵
  2. 依次反代得到结果

luogu1262间谍网络

原题传送门

题目描述

由于外国间谍的大量渗入,国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据,则称A可以揭发B。有些间谍收受贿赂,只要给他们一定数量的美元,他们就愿意交出手中掌握的全部情报。所以,如果我们能够收买一些间谍的话,我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍,他手中掌握的情报都将归我们所有,这样就有可能逮捕新的间谍,掌握新的情报。

模板---SPFA负环判定

原题传送门
题意:给定t个n点m边的图,分别判断图中有没有负环。
数据范围: N,M<=200000 ,t<=10

原题见UOJ78
有n位男生,m位女生,其中有一些男生和女生愿意结成配偶。
请问这个班级里最多产生多少对配偶?

匈牙利算法是一种用增广路求二分图最大匹配的算法。

模板---三分法

原题为luogu3382,传送门
给出一个N次函数$f$,保证在范围$[l,r]$内存在一点$x$,使得$[l,x]$上单调增,$[x,r]$上单调减。试求出$x$的值。

UOJ12 猜数

问题描述

这一天,小Y、小D、小C正在愉快地玩耍。

小Y是个数学家,他一拍脑袋冒出了一个神奇的完全平方数 $n$。

小D是个机灵鬼,很快从小Y嘴里套出了 $n$ 的值。然后在脑内把 $n$ 写成了 $a×b$的形式。其中 $a,b$都是正整数。

小C是个八卦狂,他发现小D从小Y那里获知了神奇的东西,于是死缠烂打追问小D。最后小D说道:“我可以告诉你正整数 $g$ 和 $l$ 的值,我保证 $ab=gl=n$ 且 $a,b$ 都是$g$的倍数。但是 $a,b$ 我可不能告诉你。”
这可急坏了小C。他决定退而求其次,找出$a+b$的最小值和最大值。请你帮帮他吧!

Your browser is out-of-date!

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

×