ISAP，每台机器都分成两个节点，中间连一条容量为工作效率的边；
如果输入没有1，则和源点连接，输出没有0的和汇点连接；
任意两个点之间输入和输出对应相加没有1则可以连接一条容量为INF的边。
POJ 1459 Power Network（ISAP）
Posted on
|
In
ACM
ISAP算法模板
最大流增广路算法大致有三个优化等级
- EK算法（Edmonds Karp）通过dfs每次在残量网络中找到一条可行的增广路进行增广
- Dinic算法 在每次dfs寻找增广路前，先进行一次dfs标号，流量只沿着源点到汇点之间的最短路进行增广，这就相当于给了流一个势能，水只会向下流而不会随处流动，大大所短了EK算法中发现的增广路，提高了效率
- ISAP算法，在Dinic算法的基础上进一步优化，并不需要在每次增广前都用bfs重新标号，而是只进行一次标号，之后在一个结点无法增广时才考虑修改节点的标号，同时加入一个gap优化，当某一个标号的节点个数为0时，停止增广，输出最大流。
POJ 2485 Highways
Posted on
|
In
ACM
要求能够让所有节点联通并且最大边权最小的问题，其实求的就是最小生成树的最大边权；
证明：最小生成树的最大边权一定是所有最小生成树中最小的
反证法：假设最小生成树T1的最大边(u, v)，和一个非最小生成树T2的最大边(a, b)，且(u, v) > (a, b) > T2中的其他所有边
去掉(u, v)，最小生成树会形成一个隔，u，v分别在割的两个分量中，且u，v在T2中一定存在一条唯一的路径，又由于u，v在T1中属于不同的分量，所以这条路径中一定存在着某条边两端分别在割的两个分量中，在T1中连上这条边就能够形成新的生成树，且比原来的最小生成树小，矛盾；
POJ 3026 Borg Maze
Posted on
|
In
ACM
把每个S和A都看成节点，BFS求之间的距离然后套用Prim来计算最小生成树。注意输入有坑，整数输入完后可能有多个空格，要用gets()而不能用getchar()