题目描述 如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。 输入 第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。 接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi） 输出 一行，包含一个正整数，即为该网络的最大流。 样例输入 4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40 样例输出 50 数据规模： 对于30%的数据：N<=10，M<=25 对于70%的数据：N<=200，M<=1000 对于100%的数据：N&l...

题目描述 又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。  图例（从上而下） 机场 高速铁路 飞机航线 注意：图中并没有标出所有的铁路与航线。 那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。 找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。 输入  第一行为一个正整数n(0&l...

题目描述  某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。 现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。 写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。  输入  输入文件的第一行包含两个用空格隔开的整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网...

题目描述 N(N<5000) 张矩形的海报，照片和其他同样形状的图片贴在墙上。它们的边都是垂直的或水平的。每个矩形可以部分或者全部覆盖其他矩形。所有的矩形组成的集合的轮廓称为周长。写一个程序计算周长。 图 1 是一个有 7 个矩形的例子：  图 1.一个 7 个矩形的集合对应的轮廓为图 2 所示的所有线段的集合：  图 2. 矩形集合的轮廓 所有矩形的顶点坐标均为整数。所有的坐标都在 [-10000，10000] 的范围内，并且任何一个矩形面积都为整数。结果的值可能需要 32 位有符号整数表示。 输入  第1行: N，张贴在墙上的矩形的数目 第 2..N+1行 接下来的N行中，每行都有两...

题目描述 卡德加喜欢养兔子。他在达拉然的下水道里放了 $N$ 个兔笼（编号从 $1$ 到 $N$），里面养着他从德拉诺带来的兔子。它们的繁殖遵循斐波那契数列的规律：刚开始时，笼子里有一对刚出生的兔子。每对兔子在出生第二个月后，每个月都生一对兔子。（第一个月结束后有 $1$ 对兔子。第二个月结束后有 $2$ 对。） 卡德加从苏拉玛的的大魔导师艾利桑德那边学习了先进的扭曲时空法术。有时候，他会对一排连续的兔笼（从第 $L$ 号到第 $R$ 号）释放时光流逝法术，让这些兔笼里的时间前进 $K$ 个月。另外一些时候，他想喂一下兔子，所以他想知道第 $L$ 号到第 $R$ 号兔笼里有多少只兔子。 （假设...

类似于n皇后的思想，只要把dfs表示放置情况的数字压缩成一个整数，就能实现记忆化搜索了。 一些有关集合的操作： {i}在集合S内：S&(1<<i)==1； 将{i}加入集合S：S=S|(1<<i)； 集合S内包含了{0,1,2,...,n-2,n-1}：S==(1<<n)-1；   1 #include <cstdio>  2 #include <cstring>  3 #include <cmath>  4 using namespace std;  5  6 typedef long long llt;  7 ...

这周学习了矩阵快速幂，就在这里记录下我的一下理解吧。 要学习矩阵快速幂，首先得先知道“矩阵”和“快速幂”的写法。 先说快速幂  顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为O(log₂N)，与朴素的O(N)相比效率有了极大的提高。           ——百度百科  以NOIP2013的麦森数为例题，讲一下快速幂  从文件中输入P（1000<P<3100000），计算2^P-1的位数和最后500位数字（用十进制高精度数表示）  本题显然要使用高精度运算。对2^P-1位数可以用公式log10(2^P-1)+1来求。因为2^P最后一位不可能为0，所以原式可化简为log10(2...