hdu KM匹配题集

模板 2255

  1 /*Author :usedrose  */
  2 /*Created Time :2015/8/30 1:20:31*/
  3 /*File Name :2.cpp*/
  4 #pragma comment(linker, "/STACK:1024000000,1024000000") 
  5 #include <cstdio>
  6 #include <iostream>
  7 #include <algorithm>
  8 #include <sstream>
  9 #include <cstdlib>
 10 #include <cstring>
 11 #include <climits>
 12 #include <vector>
 13 #include <string>
 14 #include <ctime>
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>
 18 #include <stack>
 19 #include <set>
 20 #include <map>
 21 #define eps 1e-8
 22 #define pi acos(-1.0)
 23 #define OK cout << "ok" << endl;
 24 #define o(a) cout << #a << " = " << a << endl
 25 #define o1(a,b) cout << #a << " = " << a << "  " << #b << " = " << b << endl
 26 using namespace std;
 27 typedef long long LL;
 28 
 29 const int N = 310;
 30 const int INF = 0x3f3f3f3f;
 31 int nx,ny;//两边的点数
 32 int g[N][N];//二分图描述
 33 int linker[N],lx[N],ly[N];//y中各点匹配状态， x,y中的点标号
 34 int slack[N];
 35 bool visx[N],visy[N];
 36 bool DFS(int x)
 37 {
 38     visx[x] = true;
 39     for(int y = 0; y < ny; y++) {
 40         if(visy[y])continue;
 41         int tmp = lx[x] + ly[y] - g[x][y];
 42         if(tmp == 0) {
 43             visy[y] = true;
 44             if(linker[y] == -1 || DFS(linker[y])) {
 45                 linker[y] = x;
 46                 return true;
 47             }
 48         }
 49         else if(slack[y] > tmp)
 50         slack[y] = tmp;
 51     }
 52     return false;
 53 }
 54 
 55 int KM()
 56 {
 57     memset(linker,-1,sizeof(linker));
 58     memset(ly,0,sizeof(ly));
 59     for(int i = 0;i < nx;i++) {
 60         lx[i] = -INF;
 61         for(int j = 0;j < ny;j++)
 62             if(g[i][j] > lx[i])
 63                 lx[i] = g[i][j];
 64     }
 65     for(int x = 0;x < nx;x++) {
 66         for(int i = 0;i < ny;i++)
 67             slack[i] = INF;
 68         while(true) {
 69             memset(visx,false,sizeof(visx));
 70             memset(visy,false,sizeof(visy));
 71             if(DFS(x))break;
 72             int d = INF;
 73             for(int i = 0;i < ny;i++)
 74                 if(!visy[i] && d > slack[i])
 75                     d = slack[i];
 76             for(int i = 0;i < nx;i++)
 77                 if(visx[i])
 78                     lx[i] -= d;    
 79             for(int i = 0;i < ny;i++) {
 80                 if(visy[i])ly[i] += d;
 81                 else slack[i] -= d;
 82             }
 83         }
 84     }
 85     int res = 0;
 86     for(int i = 0;i < ny;i++)
 87         if(linker[i] != -1)
 88             res += g[linker[i]][i];
 89     return res;
 90 }
 91 
 92 int main()
 93 {
 94     int n;
 95     while(scanf("%d",&n) == 1) {
 96         for(int i = 0;i < n;i++)
 97             for(int j = 0;j < n;j++)
 98                 scanf("%d",&g[i][j]);
 99         nx = ny = n;
100         printf("%d
",KM());
101     }
102     return 0;
103 }

View Code

【HDU】
2255 奔小康赚大钱模板题★
1533 Going Home 模板题★
2426 Interesting Housing Problem KM★
3395 Special Fish KM★
2282 Chocolate KM★
2813 One fihgt one KM★
1853 Cyclic Tour 最小费用圈覆盖★★
3488 Tour 最小费用圈覆盖★★
3435 A new Graph Game 最小费用圈覆盖★★
3722 Card Game 最小费用圈覆盖★★
3718 Similarity 求相似度★★
2448 Mining Station on the Sea 最短路+KM★★
2853 Assignment 求KM最大时,要求改动最少★★
3315 My Brute 求KM最大时,要求改动最少★★
3523 Image copy detection KM匹配,好题★★★