acronix

以下为KM算法模板：


同时BOJ 1084也是一个很裸的求二分图最佳匹配的问题。

题意：给一个n*m的方块矩阵，人和房子散乱的分布在上边，人数和房子数相等，现在要人都一动到房子里去，一人一房，人每一动一格花费为 1，问要全部人到达各自的房子的最少花费。

分析：转化为二分图最佳匹配，一边为人，一边为房子，他们之间的边权为负花费。再使用KM算法求得边权为负的最佳匹配，再取反极为最小花费了，轻松解决。

cpp代码：

#include <cstdio>
#include <memory.h>
#include <algorithm>
const int inf = -0x7fffffff;

struct Point{
       int x,y;
}h[105],m[105];

int cn,cm,cnth,cntm,map[105][105];
bool x[105],y[105];
int match[105],lx[105],ly[105],len;

bool SearchPath(int u)
{
     x[u] = true;//注意标记 
     for (int v = 1; v <= len; v++)
         if (lx[u]+ly[v] == map[u][v] && !y[v])
         {
               y[v] = true;
               if (match[v] == -1 || SearchPath(match[v]))
               {
                    match[v] = u;
                    return true;
               }
         }
     return false;
}

int KM()
{
    int i,j,k;
    int d;
    memset(ly,0,sizeof(ly));
    for (i = 1; i <= len; i++)
    {
        lx[i] = inf;
        for (j = 1; j <= len; j ++)
            if (lx[i] > map[i][j])
               lx[i] = map[i][j];
    }
    memset(match,-1,sizeof(match));
    for (i = 1; i <= len; i++)
      while (1)
     { 
        memset(x,false,sizeof(x));
        memset(y,false,sizeof(y));
        if (SearchPath(i))
            break;
        d = -inf;
        for (j = 1; j <= len; j++)
          if (x[j])
          {
                   for (k = 1; k <= len; k++)
                       if (!y[k])
                          if (d > (lx[j] + ly[k] - map[j][k]))
                             d = lx[j] + ly[k] - map[j][k];
          }
        for (j = 1; j <= len; j ++)
        {
            if (x[j])  lx[j] -= d;
            if (y[j])  ly[j] += d;  
        }
     }
    int ans = 0;
    for (i = 1; i <= len ; i++)
        ans += map[match[i]][i];
    return ans;
}

int main()
{
    int i,j,k;
    char chr[105];
    while (scanf("%d %d",&cn,&cm) && cn + cm != 0)
    {
          cnth = cntm = 0;
          for  (i = 1; i <= cn; i++)
          {
               scanf("%s",chr);
               for (j = 1; j <= cm; j++)
               {
                    map[i][j] = 0;
                    if (chr[j-1] == 'H')
                    {
                       cnth++;
                       h[cnth].x = i; h[cnth].y = j;
                    }
                    if (chr[j-1] == 'm')
                    {
                       cntm++;
                       m[cntm].x = i; m[cntm].y = j;
                    }
               }   
          }
          
          len = cnth;
          for (i = 1; i <= len; i ++)
              for (j = 1; j <= len; j++)
                map[i][j] = -(abs(h[i].x - m[j].x) + abs(h[i].y - m[j].y));
          printf("%d\n",-KM());     
                   
    }
    return 0;
}

二分图匹配算法总结

 

      二分图最大匹配的匈牙利算法 

 二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。

最大匹配： 图中包含边数最多的匹配称为图的最大匹配。 

完美匹配： 如果所有点都在匹配边上，称这个最大匹配是完美匹配。

最小覆盖： 最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数

最小路径覆盖：

用尽量少的不相交简单路径覆盖有向无环图Ｇ的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m。

最大独立集问题：

在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．

如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - 最大匹配数

 

二分图最大匹配问题的匈牙利算法：

 

 

算法思想：

 

算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.

 

一、二分图最大匹配

 

    二分图最大匹配的经典匈牙利算法是由Edmonds在1965年提出的，算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。

匈牙利算法的本质实际上和基于增广路特性的最大流算法还是相似的，只需要注意两点：

（一）每个X节点都最多做一次增广路的起点；

（二）如果一个Y节点已经匹配了，那么增广路到这儿的时候唯一的路径是走到Y节点的匹配点（可以回忆最大流算法中的后向边，这个时候后向边是可以增流的）。

    找增广路的时候既可以采用dfs也可以采用bfs，两者都可以保证O(nm)的复杂度，因为每找一条增广路的复杂度是O(m)，而最多增广n次，dfs在实际实现中更加简短。

 

二、Hopcroft-Karp算法

 

    SRbGa很早就介绍过这个算法，它可以做到O(sqrt(n)*e)的时间复杂度，并且在实际使用中效果不错而且算法本身并不复杂。

    Hopcroft-Karp算法是Hopcroft和Karp在1972年提出的，该算法的主要思想是在每次增广的时候不是找一条增广路而是同时找几条不相交的最短增广路，形成极大增广路集，随后可以沿着这几条增广路同时进行增广。

    可以证明在寻找增广路集的每一个阶段所寻找到的最短增广路都具有相等的长度，并且随着算法的进行最短增广路的长度是越来越长的，更进一步的分析可以证明最多只需要增广ceil(sqrt(n))次就可以得到最大匹配（证明在这里略去）。

    因此现在的主要难度就是在O(e)的时间复杂度内找到极大最短增广路集，思路并不复杂，首先从所有X的未盖点进行BFS，BFS之后对每个X节点和Y节点维护距离标号，如果Y节点是未盖点那么就找到了一条最短增广路，BFS完之后就找到了最短增广路集，随后可以直接用DFS对所有允许弧(dist[y]=dist[x]+1，可以参见高流推进HLPP的实现)进行类似于匈牙利中寻找增广路的操作，这样就可以做到O(m)的复杂度。

    实现起来也并不复杂，对于两边各50000个点，200000条边的二分图最大匹配可以在1s内出解，效果很好：）

 

三、二分图最优匹配

 

    二分图最优匹配的经典算法是由Kuhn和Munkres独立提出的KM算法，值得一提的是最初的KM算法是在1955年和1957年提出的，因此当时的KM算法是以矩阵为基础的，随着匈牙利算法被Edmonds提出之后，现有的KM算法利用匈牙利树可以得到更漂亮的实现。

    KM算法中的基本概念是可行顶标(feasible vertex labeling)，它是节点的实函数并且对于任意弧(x,y)满足l(x)+l(y)≥w(x,y)，此外一个概念是相等子图，它是G的一个生成子图，但是只包含满足l(xi)+l(yj)=w(xi,yj)的所有弧(xi,yj)。

    有定理：如果相等子图有完美匹配，那么该匹配是最大权匹配，证明非常直观也非常简单，反设其他匹配是最优匹配，它的权必然比相等子图的完美匹配的权要小。

    KM算法主要就是控制了怎样修改可行顶标的策略使得最终可以达到一个完美匹配，首先任意设置可行顶标（如每个X节点的可行顶标设为它出发的所有弧的最大权，Y节点的可行顶标设为0），然后在相等子图中寻找增广路，找到增广路就沿着增广路增广。

    而如果没有找到增广路呢，那么就考虑所有现在在匈牙利树中的X节点（记为S集合），所有现在在匈牙利树中的Y节点（记为T集合），考察所有一段在S集合，一段在not T集合中的弧，取

    delta =  min {l(xi)+l(yj)-w(xi,yj),xi ∈ S, yj ∈ not T}

    明显的，当我们把所有S集合中的l(xi)减少delta之后，一定会有至少一条属于(S,not T)的边进入相等子图，进而可以继续扩展匈牙利树，为了保证原来属于(S,T)的边不退出相等子图，把所有在T集合中的点的可行顶标增加delta。

    随后匈牙利树继续扩展，如果新加入匈牙利树的Y节点是未盖点，那么找到增广路，否则把该节点的对应的X匹配点加入匈牙利树继续尝试增广。

    复杂度分析：由于在不扩大匹配的情况下每次匈牙利树做如上调整之后至少增加一个元素，因此最多执行n次就可以找到一条增广路，最多需要找n条增广路，故最多执行n^2次修改顶标的操作，而每次修改顶标需要扫描所有弧，这样修改顶标的复杂度就是O(n^2)的，总的复杂度是O(n^4)的。

    事实上我现在看到的几个版本的实现都是这样实现的，但是实际效果还不错，因为这个界通常很难达到。

    对于not T的每个元素yj，定义松弛变量slack(yj) = min{l(xi)+l(yj)-w(xi,yj),xi ∈ S}，很明显的每次的delta=min{slack(yj),yj∈ not T}，每次增广之后用O(n^2)的时间计算所有点的初始slack，由于生长匈牙利树的时候每条弧的顶标增量相同，因此修改每个slack需要常数时间（注意在修改顶标后和把已盖Y节点对应的X节点加入匈牙利树的时候是需要修改slack的）。这样修改所有slack值时间是O(n)的，每次增广后最多修改n次顶标，那么修改顶标的总时间降为O(n^2)，n次增广的总时间复杂度降为O(n^3)。事实上我这样实现之后对于大部分的数据可以比O(n^4)的算法快一倍左右。

 

四、二分图的相关性质

 

    本部分内容主要来自于SRbGa的黑书，因为比较简单，仅作提示性叙述。

    (1) 二分图的最大匹配数等于最小覆盖数，即求最少的点使得每条边都至少和其中的一个点相关联，很显然直接取最大匹配的一段节点即可。

    (2) 二分图的独立数等于顶点数减去最大匹配数，很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。

(3) DAG的最小路径覆盖，将每个点拆点后作最大匹配，结果为n-m，求具体路径的时候顺着匹配边走就可以，匹配边i→j',j→k',k→l'....构成一条有向路径。

 

【最优完备匹配】

对于二分图的每条边都有一个权（非负），要求一种完备匹配方案，使得所有匹配边的权和最大，记做最优完备匹配。（特殊的，当所有边的权为1时，就是最大完备匹配问题）

KM算法：（全称是Kuhn-Munkras，是这两个人在1957年提出的，有趣的是，匈牙利算法是在1965年提出的）

为每个点设立一个顶标Li，先不要去管它的意义。

设vi,j-为(i,j)边的权，如果可以求得一个完备匹配，使得每条匹配边vi,j=Li+Lj，其余边vi,j≤Li+Lj。

此时的解就是最优的，因为匹配边的权和=∑Li，其余任意解的权和都不可能比这个大

 

定理：二分图中所有vi,j=Li+Lj的边构成一个子图G，用匈牙利算法求G中的最大匹配，如果该匹配是完备匹配，则是最优完备匹配。

 

问题是，现在连Li的意义还不清楚。

其实，我们现在要求的就是L的值，使得在该L值下达到最优完备匹配。

 

L初始化：

Li=max{wi,j}(i∈x,j∈y)

Lj=0

 

建立子图G，用匈牙利算法求G的最大匹配，如果在某点i (i∈x)找不到增广轨，则得不到完备匹配。

此时需要对L做一些调整：

设S为寻找从i出发的增广轨时访问的x中的点的集合，T为访问的y中的点的集合。

找到一个改进量dx，dx=min{Li+Lj-wi,j}(i∈S,j不∈T)

Li=Li-dx (i∈S)

Li=Li+dx (i∈T)

 

重复以上过程，不断的调整L，直到求出完备匹配为止。

 

从调整过程中可以看出：

每次调整后新子图中在包含原子图中所有的边的基础上添加了一些新边。

每次调整后∑Li会减少dx，由于每次dx取最小，所以保证了解的最优性。

 

复杂度分析：

设n为点数，m为边数，从每个点出发寻找增广轨的复杂度是O(m)，如果找不到增广轨，对L做调整的复杂度也是O(m)，而一次调整或者找到一条增广轨，或者将两个连通分量合成一个，而这两种情况最多都只进行O(n)次，所以总的复杂度是O(nm)

 

扩展：

根据KM算法的实质，可以求出使得所有匹配边的权和最小的匹配方案。

 

L初始化：

Li=min{wi,j}(i∈x,j∈y)

Lj=0

dx=min{wi,j-Li-Lj}(i∈S,j不∈T)

Li=Li+dx (i∈S)

Li=Li-dx (i∈T)

【最优匹配】

与最优完备匹配很相似，但不必以完备匹配为前提。

只要对KM算法作一些修改就可以了：

将原图转换成完全二分图（m=|x||y|），添加原图中不存在的边，并且设该边的权值为0。

题目就不说和分析了；
直接
 cpp 代码：

#include <cstdio>
#include <memory.h>

bool g[110][310],flag,vis[310];
int match[310];
int p,n;

int SearchPath(int u)
{
    for (int v = 1; v <= n; v ++)
        if (g[u][v] && ! vis[v])
        {
           vis[v] = true;
           if (match[v] == -1 || SearchPath(match[v]))
           {
              match[v] = u;
              return 1;
           }
        }
    return 0;
}

int main()
{
    int i,j,k,t,v,cnt;
    scanf("%d",&t);
    while (t--)
    {
          scanf("%d %d", &p, &n);
          for (i = 1; i <= p; i++)
              for (j = 1; j <= n; j++)
                  g[i][j] = false;
          for (i = 1; i <= n; i++)
              match[i] = -1;
          flag = true;
          for (i = 1; i <= p; i++)
          {
              scanf("%d",&k);
              if (k == 0)
                 flag = false;
              while (k--)
              {
                    scanf("%d",&v);
                    g[i][v]  = true;
              }
          }
          if (flag)
          {
               cnt = 0;
               for (i = 1; i <= p; i++)
               {
                   memset(vis,false,sizeof(vis));
                   cnt += SearchPath(i);
               }
               if (cnt == p)
                  printf("YES\n");
               else printf("NO\n");   
          } 
          else printf("NO\n"); 
    }
    
    return 0;
}

1。一个二分图中的最大匹配数等于这个图中的最小点覆盖数

【转自Matirx67】二分图最大匹配的König定理及其证明

    本文将是这一系列里最短的一篇，因为我只打算把König定理证了，其它的废话一概没有。
    以下五个问题我可能会在以后的文章里说，如果你现在很想知道的话，网上去找找答案：
    1. 什么是二分图；
    2. 什么是二分图的匹配；
    3. 什么是匈牙利算法；(http://www.matrix67.com/blog/article.asp?id=41)
    4. König定理证到了有什么用；
    5. 为什么o上面有两个点。

    König定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小点覆盖数。如果你还不知道什么是最小点覆盖，我也在这里说一下：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。比如，下面这个图中的最大匹配和最小点覆盖已分别用蓝色和红色标注。它们都等于3。这个定理相信大多数人都知道，但是网络上给出的证明并不多见。有一些网上常见的“证明”明显是错误的。因此，我在这里写一下这个定理的证明，希望对大家有所帮助。



    假如我们已经通过匈牙利算法求出了最大匹配（假设它等于M），下面给出的方法可以告诉我们，选哪M个点可以覆盖所有的边。
    匈牙利算法需要我们从右边的某个没有匹配的点，走出一条使得“一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现”的路（交错轨，增广路）。但是，现在我们已经找到了最大匹配，已经不存在这样的路了。换句话说，我们能寻找到很多可能的增广路，但最后都以找不到“终点是还没有匹配过的点”而失败。我们给所有这样的点打上记号：从右边的所有没有匹配过的点出发，按照增广路的“交替出现”的要求可以走到的所有点（最后走出的路径是很多条不完整的增广路）。那么这些点组成了最小覆盖点集：右边所有没有打上记号的点，加上左边已经有记号的点。看图，右图中展示了两条这样的路径，标记了一共6个点（用 “√”表示）。那么，用红色圈起来的三个点就是我们的最小覆盖点集。
    首先，为什么这样得到的点集点的个数恰好有M个呢？答案很简单，因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的，那么它早就当成起点被标记了；如果左边的哪个点是没有匹配过的，那就走不到它那里去（否则就找到了一条完整的增广路）。而一个匹配边又不可能左端点是标记了的，同时右端点是没标记的（不然的话右边的点就可以经过这条边到达了）。因此，最后我们圈起来的点与匹配边一一对应。
    其次，为什么这样得到的点集可以覆盖所有的边呢？答案同样简单。不可能存在某一条边，它的左端点是没有标记的，而右端点是有标记的。原因如下：如果这条边不属于我们的匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果这条边属于我们的匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的（想想匹配的定义），左端点就应该有标记。
    最后，为什么这是最小的点覆盖集呢？这当然是最小的，不可能有比M还小的点覆盖集了，因为要覆盖这M条匹配边至少就需要M个点（再次回到匹配的定义）。
    证完了。

2。最小路径覆盖=最小路径覆盖＝｜G｜－最大匹配数

 在一个N*N的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，
 且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，
 那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集．
 eg. 图4*4的图G的最小路径覆盖，包含2条路径: p1->p3, p2->p4

 由上面可以得出：

 1.一个单独的顶点是一条路径；
 2.如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的
   顶点之间存在有向边．

 最小路径覆盖就是找出最小的路径条数，使之成为G的一个路径覆盖．

 路径覆盖与二分图匹配的关系：最小路径覆盖＝｜G｜－最大匹配数；

 其中最大匹配数的求法是把G中的每个顶点pi分成两个顶点pi'与pi''，如果在p中存在一条pi到pj的边，那么在
 二分图G'中就有一条连接pi'与pj''的无向边；这里pi' 就是p中pi的出边，pj''就是p中pj 的一条入边；

 对于公式：最小路径覆盖＝｜G｜－最大匹配数；可以这么来理解；

 如果匹配数为零，那么Ｐ中不存在有向边，于是显然有：
 最小路径覆盖＝｜G｜－最大匹配数＝｜G｜－０＝｜G｜；即Ｐ的最小路径覆盖数为｜G｜；

 G'中不在于匹配边时，路径覆盖数为｜G｜;

 如果在G'中增加一条匹配边pi'->pj''，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在
 一条路径上，于是路径覆盖数就可以减少一个；如此继续增加匹配边，每增加一条，路径覆盖数就减少一条；
 直到匹配边不能继续增加时，路径覆盖数也不能再减少了，此时就有了前面的公式；但是这里只是说话了每条匹配边
 对应于路径覆盖中的一条路径上的一条连接两个点之间的有向边；下面来说明一个路径覆盖中的每条连接两个顶点之
 间的有向边对应于一条匹配边。

3。二分图最大独立集=顶点数-二分图最大匹配

独立集：图中任意两个顶点都不相连的顶点集合。

题意：就不多说了。

分析：（转的有图有真相吗）这个题目如果知道使用二分图的话就很简单了，关键就是如何构图。
cpp代码：

#include <cstdio>
#include <memory.h>

bool g[110][110]; //标记二分图的链接关系 
int match[110];//标记v中顶点匹配u的情况，无匹配则为-1 
int vis[110];
int n,m,k;

/**********************/
int SearchPath(int u)
{
    for (int v = 1; v <= m; v ++)
        if (g[u][v] && !vis[v])
        {
            vis[v] = true;
            if (match[v] == -1 || SearchPath(match[v]))
            {
                 match[v] = u;
                 return 1;
            }
        }
    return 0;
}
                /**********************************/

int main()
{
    int i,j,x,y,ans;
    while (scanf("%d",&n) && n != 0)
    {
          scanf("%d %d", &m, &k);
          for (i = 1; i <= n; i++)
              for (j = 1; j <= m; j ++)
                  g[i][j] = false;
              
          for (i = 1; i <= k; i ++)
          {
              scanf("%d %d %d", &j, &x, &y);
              g[x][y] = true; 
          }
/**********/
          memset(match,-1,sizeof(match));
          ans = 0;
          for (i = 1; i <= n; i++)
          {
              memset(vis,false,sizeof(vis));
              ans += SearchPath(i);
          } 
                /**************************/
          printf("%d\n",ans);   
          
    }
    
    return 0;
}

POJ推荐50题 —— 参加10年暑假集训时要求完成

 

记住写解题报告和解题总结！！
 
  
 
POJ == 北京大学ACM在线评测系统 http://acm.pku.edu.cn/JudgeOnline

第一类 动态规划 (至少6题，2479 and 2593必做)
 
2479 and 2593
 
1015
 
1042 (也可贪心)
 
1141
 
1050
 
1080
 
1221
 
1260
 
2411 (稍难)
 
1276
 
 
 
第二类 搜索 (至少4题)
 
1011
 
1033
 
1129
 
2049
 
2056
 
2488
 
2492 (稍难，也可并查集)
 
 
 
第三类 贪心 (至少2题)
 
1065
 
2054 (难)
 
1521
 
2709
 
 
 
第四类 最短路 (至少3题) 
 
1062 昂贵的聘礼(直接dfs，或者枚举等级区间+floyd)
 
1125 Stockbroker Grapevine （Prim求两两最短路）
 
1797Heavy Transportation (Dijsktra的变形，实质贪心)
 
2253 （同1797，贪心）

上两题贪心（Dijsktra）的证明
d[i] = max ( d[i], min（d[u], map[u][i]）) d[u]是当前进入访问点集合的点。
S为已访问的点集。

定理 每次加入的S的点u，d[u]就是题目所求最大载重。
证明
每次加入S的点u为当前d值最大的点，所以未访问的点集中没有点可以对u进行松弛操作(若t能对u进行松弛操作，

则有d[t]>d[u])。而S中的顶点也都进行了松弛操作，所以D的值不会改变。定理得证。

 

亦可用Floyd，稍作修改即可，而dis[i][j]意义为 i ，j 之间符合题意的最优值，

在三重循环用k值不断更新dis[i][j]

具体见：http://blog.sina.com.cn/s/blog_5f5353cc0100gnxu.html

               据说还能用最小生成树和最大生成树做上两题，会了再说吧

 

 
2679 Bellman-Ford (难)
 
 
 
第五类 最小生成树 (至少2题, 而且 Prim 和 Kruskal 至少各用一次)
 
1251
 
1258
 
1789
 
2485
 
 
 
第六类 最大流 (至少2题)

 
1087 A Plug for UNIX(dinic模板完美使用)
 
1459 Power Network（dinic模板完美使用）
 
1149 Pigs(建模得动点脑筋)

 

1966
 
2516 (最小费用最大流) (难) 
 
2711

 

3469  

 

3498

 
第七类 二分图 (至少3题)
 
1325 Machine Schedule(匈牙利算法初步)
 
1469 course（全裸的二分最大匹配）
 
2195 (KM 算法或最小费用最大流) (难)
 
2446
 
1422 and 2594
 
 
 
第八类 并查集 (至少2题)
 
1861
 
1182 (难)
 
1308
 
2524
 
 
 
第九类 快速查找 (B-Search, Hash and so on) (至少3题)
 
2503
 
2513 (+Euler回路的判定)
 
1035
 
1200
 
2002
 
 
 
第十类 数论 (至少2题)
 
1061
 
1142
 
2262
 
2407
 
1811(难)
 
2447 (难)
 
 
 
第十一类 线段树 (无最少题数要求)
 
2352 (可用简单方法)
 
2528
 
 
 
第十二类 计算几何 (至少2题，1113凸包算法必做)
 
1113
 
1292
 
2148 (难)
 
2653
 
1584
 
 
 
第十三类 高精度 (至少3题，1001必做)
 
1001
 
1047
 
1131
 
1503
 
1504
 
1060 and 1996 (多项式)
 
SCU1002, 1003, 1004 (http://acm.scu.edu.cn/soj)
 
 
 
第十四类 模拟 (至少5题)
 
1029 and 1013
 
1083 and 2028
 
2234 and 1067
 
1012
 
1026
 
1068
 
1120
 
2271
 
2632
 
 
 
第十五类 数学 (至少4题)
 
2249
 
1023
 
2506
 
1079
 
1019 and 1095
 
1905 and 1064 (二分) 
 
  
 
http://forum.byr.edu.cn/wForum/board.php?name=ACM_ICPC
 
BUPT ACM FTP
 
Address: ftp://www.cs.bupt.cn/acm
 
ID: acmguest
 
PASSWORD: acmftp

题意：电脑装机，要买 N 个配件，现有两家公司A 、B分别有这些配件，但价格不同，现在要求买完配件所用最少的价钱，同时若两配件来自不同的公司，考虑兼容性，可能要花而外的钱买转换器。

分析：最小割转换到最大流，n个配件，n个顶点，源点连向各顶点的边表示A公司的配件，边权表示A公司的该配件的价钱;各顶点连向汇点的边表示B公司的配件，边权表示B公司的该配件的价格。当两配件来自不同公司有兼容性问题时，对应的顶点连双向边，边权为转换器的价格。构图完成，很显然，此图的最小割便是所求，因而可用求最大流即可。

收获：因为此题数据顶点和边的数量都很大，朴素的最大流勉强能应付，但用dinic求最大流，那速度可是相当的快，几倍的差别，甚至是TLE 和 AC的差别。所以好好用好魅力无穷的Dinic吧~~~


cpp代码：

以下解析来自：http://imlazy.ycool.com/post.2059102.html

PKU 1149， PIGS，构造网络流模型时，要注意合并节点和边

  这道题目的大意是这样的：

• 有 M 个猪圈（M ≤ 1000），每个猪圈里初始时有若干头猪。
• 一开始所有猪圈都是关闭的。
• 依次来了 N 个顾客（N ≤ 100），每个顾客分别会打开指定的几个猪圈，从中买若干头猪。
• 每个顾客分别都有他能够买的数量的上限。
• 每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。

    问总共最多能卖出多少头猪。

    举个例子来说。有 3 个猪圈，初始时分别有 3、 1 和 10 头猪。依次来了 3 个顾客，第一个打开 1 号 和 2 号猪圈，最多买 2 头；第二个打开 1 号 和 3 号猪圈，最多买 3 头；第三个打开 2 号猪圈，最多买 6 头。那么，最好的可能性之一就是第一个顾客从 1 号圈买 2 头，然后把 1 号圈剩下的 1 头放到 2 号圈；第二个顾客从 3 号圈买 3 头；第三个顾客从 2 号圈买 2 头。总共卖出 2 + 3 + 2 = 7 头。□

    不难想像，这个问题的网络模型可以很直观地构造出来。就拿上面的例子来说，可以构造出图 1 所示的模型（图中凡是没有标数字的边，容量都是 +∞）：

• 三个顾客，就有三轮交易，每一轮分别都有 3 个猪圈和 1 个顾客的节点。
• 从源点到第一轮的各个猪圈各有一条边，容量就是各个猪圈里的猪的初始数量。
• 从各个顾客到汇点各有一条边，容量就是各个顾客能买的数量上限。
• 在某一轮中，从该顾客打开的所有猪圈都有一条边连向该顾客，容量都是 +∞。
• 最后一轮除外，从每一轮的 i 号猪圈都有一条边连向下一轮的 i 号猪圈，容量都是 +∞，表示这一轮剩下的猪可以留到下一轮。
• 最后一轮除外，从每一轮被打开的所有猪圈，到下一轮的同样这些猪圈，两两之间都要连一条边，表示它们之间可以任意流通。

 

    不难想像，这个网络模型的最大流量就是最多能卖出的数量。图中最多有 2 + N + M × N ≈ 100,000 个节点。□

    这个模型虽然很直观，但是节点数太多了，计算速度肯定会很慢。其实不用再想别的算法，就让我们继续上面的例子，用合并的方法来简化这个网络模型。

    首先，最后一轮中没有打开的猪圈就可以从图中删掉了，也就是图 2 中红色的部分，显然它们对整个网络的流量没有任何影响。

    接着，看图 2 中蓝色的部分。根据我总结出的以下几个规律，可以把这 4 个点合并成一个：

    规律 1. 如果几个节点的流量的来源完全相同，则可以把它们合并成一个。

    规律 2. 如果几个节点的流量的去向完全相同，则可以把它们合并成一个。

    规律 3. 如果从点 u 到点 v 有一条容量为 +∞ 的边，并且 u 是 v 的唯一流量来源，或者 v 是 u 的唯一流量去向，则可以把 u 和 v 合并成一个节点。

    根据规律 1，可以把蓝色部分右边的 1、 2 号节点合并成一个；根据规律 2，可以把蓝色部分左边的 1、 2 号节点合并成一个；最后，根据规律 3，可以把蓝色部分的左边和右边（已经分别合并成了一个节点）合并成一个节点。于是，图 2 被简化成了图 3 的样子。也就是说，最后一轮除外，每一轮被打开的猪圈和下一轮的同样这些猪圈都可以被合并成一个点。

    接着，根据规律 3，图 3 中的蓝色节点、2 号猪圈和 1 号顾客这三点可以合并成一个；图 3 中的两个 3 号猪圈和 2 号顾客也可以合并成一个点。当然，如果两点之间有多条同向的边，则这些边可以合并成一条，容量相加，这个道理很简单，就不用我多说了。最终，上例中的网络模型被简化成了图 4 的样子。□

 

    让我们从图 4 中重新总结一下构造这个网络模型的规则：

• 每个顾客分别用一个节点来表示。
• 对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。
• 对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i ∈ [1, n)，从该猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为 +∞。
• 从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。

    拿我们前面一直在讲的例子来说：1 号猪圈的第一个顾客是 1 号顾客，所以从源点到 1 号顾客有一条容量为 3 的边；1 号猪圈的第二个顾客是 2 号顾客，因此从 1 号顾客到 2 号顾客有一条容量为 +∞ 的边；2 号猪圈的第一个顾客也是 1 号顾客，所以从源点到 1 号顾客有一条容量为 1 的边，和之前已有的一条边合并起来，容量变成 4；2 号猪圈的第二个顾客是 3 号顾客，因此从 1 号顾客到 3 号顾客有一条容量为 +∞ 的边；3 号猪圈的第一个顾客是 2 号顾客，所以从源点到 2 号顾客有一条容量为 10 的边。□

    新的网络模型中最多只有 2 + N = 102 个节点，计算速度就可以相当快了。可以这样理解这个新的网络模型：对于某一个顾客，如果他打开了猪圈 h，则在他走后，他打开的所有猪圈里剩下的猪都有可能被换到 h 中，因而这些猪都有可能被 h 的下一个顾客买走。所以对于一个顾客打开的所有猪圈，从该顾客到各猪圈的下一个顾客，都要连一条容量为 +∞ 的边。

    在面对网络流问题时，如果一时想不出很好的构图方法，不如先构造一个最直观，或者说最“硬来”的模型，然后再用合并节点和边的方法来简直化这个模型。经过简化以后，好的构图思路自然就会涌现出来了。这是解决网络流问题的一个好方法。

    代码就不贴了，网络流的题目还是重在建模和思维转化。

//考察点: 着色原理 BFS 邻接表建图
//思路: 先BFS,在BFS的过程中标记到达某点时的步数的奇偶性.
//提交情况: 3WA 1AC
第一次WA是因为判断是否相连的时候就错了 后来的两次WA是因为没有初始化VIS数组,这个是我的老毛病了要更正!
//收获: 学习到了用邻接表建图的皮毛 熟悉了用邻接表去建一个图的方法
//经验: 写好代码以后一定要想象一下处理每个CASE都用到了哪些东西 用完之后都要想是不是需要初始化.!!!!很重要的一个习惯. 要养成这种好的编程习惯.
// ACcode