二分图的最小点权覆盖，选定点集，与该点集有关的边覆盖所有顶点，且该点集的点权值和最小。

有类似于匈牙利算法一样的带权匹配算法，但是这里就不介绍了。个人比较推荐，用最大流算法更好理解，写起来更容易。

题意：一个m X n的方阵，方阵格子中有老鼠屎，神枪手一枪能打掉一行或者一列上的所有赃物，让选定某些行和某些列，打掉所有赃物。已知条件： m、n，老鼠屎l粒，在每一行和列上布置神枪手的花费ci、cj，l粒老鼠屎的坐标。总费用为选定的行和列对应的花费值乘积，求最小总费用。

第一步：化积为和，使用幂函数，最后得到结果时再还原！！！

第二步：最大流算法求最小点权覆盖。

先弱弱证明一下该算法。坐标为(i,j)的老鼠屎，第i行和第j列必选之一，点覆盖必选边两个端点之一。假设仅有某一行i上，第a、b、c（可以更多）列上有老鼠屎，选定i行或者选定对应的所有列，也即两者之一必有一个是在最小割中。

• 若（条件1）Α第i行的费用小于所有列，选行i，否则（条件2）选列。
• 若再有某一行ii（ii != i）有a、b、d、e列上有老鼠屎，若上一步（条件1）为真，ii行的费用减去第i行中行与列的差（此差值也进入最小割，当然有可能行ii的费用更小，那样就是ii的费用进入最小割了）否则，对于此行a、b就不考虑，行ii与 d、e列像上一步一样考虑。
• 把i行和ii行看成一行，继续对后面的行进行第二步判定。

此最小点权覆盖就和最小割联系起来了。

只是个博客，写的不是特别学术，希望读者能看懂。

贴个代码，祝好运！

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 using namespace std;  7 #define maxn 500  8 const int maxe = 1001000;  9 const double maxf = 1e10; 10 #define zero 1e-8 11 struct edge{ 12     int u,v; double c; 13     edge(int e1=0,int e2=0,double e3=0){ u=e1,v=e2; c=e3; } 14 }e[maxe]; 15 int ec; 16 int head[maxn]; 17 int next[maxe]; 18 void addedge(int u,int v,double c){ 19     e[ec]=edge(u,v,c); 20     next[ec]=head[u]; head[u]=ec++; 21     //printf("%d --> %d , c = %.5f\n",u,v,c); 22     e[ec]=edge(v,u,0); 23     next[ec]=head[v]; head[v]=ec++; 24 } 25 //***********************************// 26 int source,sink,maxdep; 27 int dep[maxn],gap[maxn]; 28 void setGD(){ 29      for(int i=0;i<=maxdep;i++) dep[i] = maxdep; dep[sink] = 0; 30      int u,v; 31      queue
           
             que; 32 que.push(sink); 33 while(!que.empty()){ 34 u = que.front(); que.pop(); 35 for(int i=head[u];i!=-1;i=next[i]){ 36 v = e[i].v; //if(v > maxdep) continue; 37 if(dep[v] < maxdep) continue; //'被访问过' 38 dep[v] = dep[u]+1; 39 que.push(v); 40 } 41 } 42 memset(gap,0,sizeof(gap)); 43 for(int i=0;i<=maxdep;i++) gap[dep[i]]++; 44 } 45 double maxF(){ 46 setGD(); 47 int u=source,i; 48 int cur[maxn],trace[maxn],top=0; 49 for(int i=0;i<=maxdep;i++) cur[i] = head[i]; 50 double flow=0; 51 while(dep[source] <= maxdep){ 52 if(u == sink){ 53 double tf = maxf; int ins; 54 for(i=0;i
            
              0) 56 tf = e[trace[i]].c, ins = i; 57 for(i=0;i
             
               zero && dep[u] == dep[e[i].v] + 1) 67 break; 68 if(i != -1) { 69 trace[top++] = i; 70 cur[u] = i; 71 u = e[i].v; 72 } 73 else { 74 int mindep = maxdep; 75 for(i=head[u];i!=-1;i=next[i]){ 76 if(e[i].c > zero && dep[e[i].v] < mindep) 77 mindep = dep[e[i].v], cur[u] = i; 78 } 79 gap[dep[u]]--; 80 dep[u] = mindep + 1; 81 gap[dep[u]]++; 82 if(u != source) 83 u = e[trace[--top]].u; 84 } 85 } 86 return flow; 87 } 88 //**********************************// 89 void initial(){ 90 ec = 0; 91 memset(head,-1,sizeof(head)); 92 //initial source ,sink and maxdep; 93 } 94 int main() 95 { 96 int cases; cin>>cases; 97 int n,m,l; 98 for(int cas=0;cas