题意：现在有N个人和N个位置，每个人只能站在某个位置一次，并且每个位置只能站一个人（就是说一个位置上不能有两个人），最后求有多少种站法，并把每种站法输出。 输出的格式为：第几个位置站哪个人。 思路：如果求有多少种站法可以用二分法。。算出具体有ans种方法。 s->u 边权为mid u->v 第u个人站在第v个位置( 1 <= u <= n  n < v <= 2n ) v->t 边权为mid 我是用Dinic计算的。然后把答案ans Dinic后残留网络中的还有流量的边给删掉。 然后再跑ans次，每次建图还是同上。 s->u 边权为1 u->v 第u个人站在第v个位置( 1 <= u <= n  n < v <= 2n) v->t 边权为1 每次跑完Dinic后可以算出有哪些位置可以站。 然后把对应的边给去掉。 代码： #include <iostream>#include <cstdio>#include <cstring>#include <cmath&g ...

。。。这题看的是其他人才做出来的。。汗颜。原来可以这么做。。 链接：http://blog.csdn.net/weiguang_123/article/details/8077385 //author: CHC//Last Edit Time: 2014-12-10 15:34#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1e+7;const int INF = numeric_limits& ...

-finput-charset=GBK -fexec-charset=GBK 这个和vim本身没有关系。。 加入编译参数就行了。。

这题真的坑。。。题意晦涩难懂。出题人你真是够了 题意：有n个城市需要建设道路，有m个公司可以工作。每个公司在开始工作前需要给政府税收，一个公司如果工作了一定必须完成它所负责的那些路段。所花的费用由政府来出。如果X公司建设了a->b路段，Y公司建设了b->c路段。那么我们称X公司和Y公司有单向关系X->Y，规定：如果X工作了，那么和X有关系的公司都要工作。。 求政府最多能赚多少钱。 建图模型： 完成某件事之前必须完成另一件事。这种模型非常经典。 最大权闭合图 在胡伯涛的《最小割模型在信息学竞赛中的应用》中提及。 做法： u->v u公司和v公司有直接联系，边权为INF s->u 如果招标u公司的收益s > 0(s=税收-铺设边所花的费用总和)，边权为s v->t 如果招标v公司的收益s < 0(s同上)，边权为-s 这个模型所求得的最小割(s-t)满足的条件为： 政府的最小花费 所有税收(s > 0)之和-最小花费=最大收益 为什么？。割边集只能是简单割边集：s->u或者v->t，不存在u->v。 若s->u是 ...

题意：有n个可选信息站要建立，每个信息站建立需要一定的代价，有m个反馈说某两个站之间建立联系的话会有一定收益。现要求最大收益。 模型： 最大权闭合图。 建图： 若(u,v)建立边权可以获得w的收益 u->k 边权为INF v->k 边权为INF k->t 边权为w 初始化： s->x 边权为建立编号为x的信息站需要花费的代价 代码： //author: CHC//First Edit Time: 2014-12-04 13:14//Last Edit Time: 2014-12-04 13:48#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include < ...

题意：给定一个有向图，A在1点，B在n点。B为了抵制A可以摧毁一些边，但A可以永久加固一条边使得不可摧毁。 A要怎么加固使得B花费的代价最大。 模型： 首先跑一次1->n的最大流，然后找s集合和t集合，就是从1出发所能到达的集合(不经过满流边)，反之就是t集合了。 这个时候我可以这么做。新建一个中立节点st1，判断从1出发所能产生的第二次最大流是多少。从st1出发到n所能长生的最大流是多少。取两者的最小值。 代码： //author: CHC//First Edit Time: 2014-11-30 10:33//Last Edit Time: 2014-12-02 21:10#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#incl ...

题意：给定一个有向图，伏地魔在0号节点。城堡在n-1号节点。拆掉每一条路有一些代价，现在询问需要最少代价拆掉最少的边是多少。输出边数。 模型： 最小割找最少边。 状态压缩。。 代码： //author: CHC//First Edit Time: 2014-11-29 23:36//Last Edit Time: 2014-11-30 10:17#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1 ...

题意：给定一颗树，树的边权就是剪短这条边需要的代价。现在需要减掉这颗树的叶子。。需要的最少代价是多少。 裸的最小割模型。。。 代码： #include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+3 * 2;const int MAXM=1e+5 * 2 + 100;const int INF = numeric_limits<int>::max();const LL LL_INF= numeric_limits<LL> ...

题意：国王给你f城市选择(可以选多个)。但是不希望存在可以从首都走到你的城市的路径。每个城市可以有一定的收益，但是删除一些路要付出一些代价。问可以获取的最大代价是多少并输出需要拆掉的边。 模型就是 找最大流的割边。。 代码： #include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+3 * 2;const int MAXM=1e+5 * 2 + 100;const int INF = numeric_limits<int>:: ...

题意：给定一个有向图，给一对点(s,t)，可删除点的定义为：删除某个点之后使得s没有路径到达t，问有多少个可删除点。 思路： 想法1： 这题一开始我的思路就是用网络流来做。。就是先跑s->t的网络流，若最大流量==1则代表存在关键点，否则不存在关键点(>1和==0的情况分别讨论)，然后找关键点就是每次找到可通过的边的最远的那个点开始第二次跑网络流。。之后。。发现不好处理。所以路就断了。。 之后我再想了其他方法来做。 想法2： 就是标记这些点 s–>x–> …->t 在图中把类似这种的x点标记，建立残图，这个时候残图一定是包含有关s->t的路径的。其他无关路径都没有加进来。再之后把这个有向图给弄成无向图。找割点。割点的个数+2就是答案了。。 后来发现太天真了。 碰到这种结构就完了。。看图。。 红色的点是割点。。但是红色的点并不是关键点。。我就丧心病狂的交了好多发最后还是无情的挂了。。 这种方法不行。。那就换思路吧。。 想法3： 突然想到。。先随意找一条s->t的路径。那么可删除点一定在这条路径上。因为除了这条路径的其他点一定不是可删除点。 那么问 ...