比赛链接：http://acm.hrbust.edu.cn/vj/index.php?c=contest-contest&cid=160
A：HDU 2063 过山车
Hungary求最大匹配简单题
代码：
#include <stdio.h> #include <string.h> #include <iostream> #include <queue> using namespace std; #define siz 2100 int mp[siz][siz]; int n, m; int ans; bool vis[siz]; int link[siz]; int nx, ny; bool find_(int x) { for (int i=1; i<=ny; ++i) { if (mp[x][i] && !vis[i]) { vis[i] = 1; if (link[i] == -1 || find_(link[i])) { link[i] = x; return true; } } } return false; } void match() { ans = 0; memset(link, -1, sizeof(link)); for (int i=1; i<=nx; ++i) { memset(vis, 0, sizeof(vis)); if (find_(i)) ans++; } return; } int main() { int k, m, n; while(cin >> k) { if (k == 0) break; cin >> m >> n; nx = m, ny = n; memset(mp, 0, sizeof(mp)); for (int i=0; i<k; ++i) { int a, b; cin >> a >> b; mp[a][b] = 1; } match(); cout << ans << endl; } return 0; }
B:POJ 3041 Asteroids
二分图行列建模、求最小点覆盖即为ans.
代码：
#include <stdio.h> #include <string.h> #include <iostream> #include <queue> using namespace std; #define siz 2100 int mp[siz][siz]; int n, m; int ans; bool vis[siz]; int link[siz]; int nx, ny; bool find_(int x) { for (int i=1; i<=ny; ++i) { if (mp[x][i] && !vis[i]) { vis[i] = 1; if (link[i] == -1 || find_(link[i])) { link[i] = x; return true; } } } return false; } void match() { ans = 0; memset(link, -1, sizeof(link)); for (int i=1; i<=nx; ++i) { memset(vis, 0, sizeof(vis)); if (find_(i)) ans++; } return; } int main(){ while ( ~scanf("%d%d", &n ,&m) ){ memset(mp, 0, sizeof(mp)); nx = n; ny = n; while ( m-- ){ int a, b; scanf("%d%d", &a, &b); mp[a][b] = 1; } match(); printf("%d ", ans); } return 0; }
C：HDU 4160 dolls
题意：盒子包小盒子，问最后剩下可见的盒子最少有多少个。
思路：把盒子看成点，大盒子与可以放入的小盒子建有向边，该有向图的最小路径覆盖,拆点得到对应二分图的n-最大匹配数即为ans。
代码：
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define N 555 int link[N][N]; int mark[N]; int visited[N]; struct node{ int a,b,c; }s[N]; int n; int dfs(int x) { int i; for(i=1;i<=n;i++) { if(link[x][i]==0) continue; if(visited[i]==1) continue; { visited[i]=1; if(mark[i]==0||dfs(mark[i])==1) { mark[i]=x; return 1; } } } return 0; } int main() { while(cin>>n) { if(n==0) break; int i; memset(link,0,sizeof(link)); memset(s,0,sizeof(s)); memset(mark,0,sizeof(mark)); for(i=1;i<=n;i++) cin>>s[i].a>>s[i].b>>s[i].c; int j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(s[i].a<s[j].a&&s[i].b<s[j].b&&s[i].c<s[j].c) link[i][j]=1; } int num=0; for(i=1;i<=n;i++) { memset(visited,0,sizeof(visited)); if(dfs(i)==1) num++; } printf("%d ",n-num); } return 0; }
D：HDU 2255 奔小康赚大钱
km求最大权匹配简单题
代码：
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; #define siz 310 #define inf 100000000 int mp[siz][siz]; int link[siz]; int visx[siz], visy[siz]; int lx[siz], ly[siz]; int slack[siz]; int n, nx, ny; bool find_(int x) { visx[x] = 1; for (int y=1; y<=ny; ++y) { if (visy[y]) continue; // 如果已经被访问过 int w = lx[x] + ly[y] - mp[x][y]; if (w == 0) { visy[y] = 1; if (link[y] == -1 || find_(link[y])) { link[y] = x; return true; } } else { slack[y] = min(slack[y], w); } } return false; } int km() { // 初始化可行顶标 memset(ly, 0, sizeof(ly)); for (int i=1; i<=nx; ++i) { lx[i] = -inf; for (int j=1; j<=ny; ++j) { lx[i] = max(lx[i], mp[i][j]); } } memset(link, -1, sizeof(link)); for (int x=1; x<=nx; ++x) { // 从左集合依次寻找增广路 for (int y=1; y<=ny; ++y) { slack[y] = inf; } while(1) { memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if (find_(x)) break; // 如果找到增广路 int d = inf; // 否则修改可行顶标 for (int y=1; y<=ny; ++y) { if (!visy[y]) d = min(d, slack[y]); } for (int i=1; i<=nx; ++i) { if (visx[i]) lx[i] -= d; } for (int i=1; i<=ny; ++i) { if (visy[i]) ly[i] += d; else slack[i] -= d; } } } int ans = 0; for (int y=1; y<=ny; ++y) { if (link[y] != -1) { ans += mp[link[y]][y]; } } return ans; } int main() { while(~scanf("%d", &n)) { for (int i=1; i<=n; ++i) { for (int j=1; j<=n; ++j) { int val; scanf("%d", &val); mp[i][j] = val; // 表示第I个村民对第j间房子的出价 } } nx = n; ny = n; int ans = km(); printf("%d ", ans); } return 0; }
E：HDU 3605 Escape
匈牙利算法的应用，解决多重匹配问题
左集合的多个点可以同时匹配右集合的同一个点。在匈牙利算法的基础上判断是不是达到最大人数即可。
代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,m; int w[15],cnt[15]; int mp[100010][12],mat[12][100010]; bool vis[15]; bool find_(int x) { for(int i=0;i<m;i++) if(!vis[i]&&mp[x][i]) { vis[i]=1; if(cnt[i]<w[i]) // 如果这个星球上的人数还没有到最大值 { mat[i][cnt[i]++]=x; //x是i星球的第cnt[i]个人 return true; } for(int j=0;j<cnt[i];j++) // 否则遍历这个星球上的所有人，看是否有人能找到别的星球 if(find_(mat[i][j])) { mat[i][j]=x; return true; } } return false; } bool match() { memset(cnt,0,sizeof(cnt)); for(int i=0;i<n;i++) { memset(vis,0,sizeof(vis)); if(!find_(i)) return false; } return true; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&mp [i][j]); for(int i=0;i<m;i++) scanf("%d",&w[i]); if (match()==1) // 如果每个人都找到了自己所在的星球 printf ("YES "); else printf ("NO "); } return 0; }
F： HDU 1281 棋盘游戏
行列建模求二分图最大匹配，依次去掉每个点，如果此时找到的最大匹配不变，则该点不是重要点，否则是。
代码：
#include <stdio.h> #include <string.h> #include <iostream> #define siz 310 using namespace std; int mp[siz][siz]; int vis[siz]; int link[siz]; int n, m; int match[siz]; bool find_(int x) { for (int i=1; i<=m; ++i) { if (!vis[i] && mp[x][i]) { vis[i] = 1; if (link[i] == -1 || find_(link[i])) { link[i] = x; return true; } } } return false; } int Hungary() { memset(link, -1, sizeof(link)); int ans = 0; for (int i=1; i<=n; ++i) { memset(vis, 0, sizeof(vis)); if (find_(i)) ans++; } return ans; } int main() { int k; int cnt = 0; while(~scanf("%d%d%d", &n, &m, &k)) { memset(mp, 0, sizeof(mp)); for (int i=0; i<k; ++i) { int x, y; scanf("%d%d", &x, &y); mp[x][y] = 1; } int ansm = Hungary(); //cout << ansm << "+++++ "; int ansp = 0; for (int i=1; i<=m; ++i) { match[i] = link[i]; } for (int i=1; i<=m; ++i) { if (match[i] != -1) { mp[match[i]][i] = 0; int temp = Hungary(); if (temp != ansm) { ansp++; } mp[match[i]][i] = 1; } } printf("Board %d have %d important blanks for %d chessmen. ", ++cnt, ansp, ansm); } return 0; }
G：POJ 1469 COURSES
Hungary求最大匹配，判断是不是完备匹配
代码：
/* HDU 1083 有P个课程，N 个同学，给出每个课程被哪些同学访问过了，访问过这个课程的人，就可以代表这个课程。 询问，是否能找到P个同学的group，使得，每个同学代表不同的课程，然后，每个课程都有人代表。 即，是否存在课程集合的完备匹配。 */ #include <stdio.h> #include <string.h> #include <iostream> #define siz 310 using namespace std; int mp[siz][siz]; int link[siz]; int vis[siz]; int P, N; bool find_(int x) { for (int i=1; i<=N; ++i) { if (mp[x][i] && !vis[i]) { vis[i] = 1; if (link[i] == -1 || find_(link[i])) { link[i] = x; return true; } } } return false; } int Hungary() { memset(link, -1, sizeof(link)); int ans = 0; for (int i=1; i<=P; ++i) { memset(vis, 0, sizeof(vis)); if (find_(i)) ans++; } return ans; } int main() { int t; scanf("%d", &t); while(t--) { scanf("%d%d", &P, &N); memset(mp, 0, sizeof(mp)); // build map for (int i=1; i<=P; ++i) { int tot; scanf("%d", &tot); for (int j=1; j<=tot; ++j) { int temp; scanf("%d", &temp); mp[i][temp]++; } } //build map end int ans = Hungary(); if (ans == P) { printf("YES "); } else printf("NO "); } return 0; }
H：HDU 3488 Tour
多个环的并。求出对应二分图的最大匹配即为ans，注意边权开始初始化为-inf。
代码：
#include <stdio.h> #include <string.h> #include <iostream> #define siz 310 #define inf 100000000 using namespace std; int lx[siz], ly[siz]; // 可行顶标集合 int slack[siz]; int visx[siz], visy[siz]; int mp[siz][siz]; // 边的集合 int link[siz]; // 匹配集合 int n, nx, ny; // 点的个数 左集合点的个数 和右集合点的个数 bool dfs(int x) { visx[x] = 1; // 左集合访问到的点一定都在交错树中------------- for (int i=1; i<=ny; ++i) { if (visy[i]) continue; int w = lx[x] + ly[i] - mp[x][i]; if (w == 0) { visy[i] = 1; // 右集合的点在相等子图中 就一定在交错树中------------ if (link[i] == -1 || dfs(link[i])) { link[i] = x; return 1; } } else slack[i] = min(slack[i], w); // 修改不在相等子图中的点 的slack值 } return 0; } int km() { memset(link, -1, sizeof(link)); // lx 和 ly的初始化 memset(ly, 0, sizeof(ly)); for (int i=1; i<=nx; ++i) { lx[i] = -inf; for (int j=1; j<=ny; ++j) { lx[i] = max(lx[i], mp[i][j]); } } // 从x集合的每个点寻找增广路 for (int x=1; x<=nx; ++x) { for (int i=1; i<=ny; ++i) { //slack 的初始化对当前点寻找增广路的左右过程中有效----------- slack[i] = inf; } //cout << x << "=== "; while(1) { memset(visx, 0, sizeof(visx)); //每次寻找增广路之前初始化---------- memset(visy, 0, sizeof(visy)); if (dfs(x)) break; //该点增广完成 // 否则修改可行顶标 int d = inf; for (int i=1; i<=ny; ++i) { if (!visy[i]) d = min(d, slack[i]); } for (int i=1; i<=nx; ++i) { if (visx[i]) lx[i] -= d; } for (int i=1; i<=ny; ++i) { if (visy[i]) ly[i] += d; else slack[i] -= d; } } } int res = 0; for (int i=1; i<=ny; ++i) { //必定已经找到一个所有相等子图的点导出的完美匹配--------- if (link[i] != -1) res += mp[link[i]][i]; // 右集合i的匹配点link[i] 这里不像无向图那样，需要注意顺序--------- } return res; } int main() { int t; cin >> t; while(t--) { int m; cin >> n >> m; nx = n, ny = n; for (int i=1; i<=n; ++i) { for (int j=1; j<=n; ++j) { mp[i][j] = -inf; // 注意初始化为-inf } } for (int i=0; i<m; ++i) { int u, v, w; cin >> u >> v >> w; if (-w > mp[u][v]) mp[u][v] = -w; } int ans = -km(); cout << ans << endl; } return 0; }
I：HDU 1045 Fire Net
二分图多行多列建模
代码：
/* HDU 1045 */ #include <stdio.h> #include <string.h> #include <iostream> #include <vector> #define siz 25 #define inf 100000000 using namespace std; char mpp[siz][siz]; struct Node { int x, y; }; int n; Node p[siz][siz]; int maxr, maxc; int link[siz]; int vis[siz]; int mp[siz][siz]; int nx, ny; bool find_(int x) { for (int i=1; i<=ny; ++i) { if (mp[x][i] && !vis[i]) { // 有边相连 vis[i] = 1; // 标记该点 if (link[i] == -1 || find_(link[i])) { //该点未匹配 或者匹配的点能找到增光路 link[i] = x; // 删掉偶数条边 加进奇数条边 return true; // 找到增光路 } } } return false; } int match() { //初始化 nx = maxr, ny = maxc; int ans = 0; memset(link, -1, sizeof(link)); for (int i=1; i<=nx; ++i) { memset(vis, 0, sizeof(vis)); // 从集合的每个点依次搜索 if (find_(i)) // 如果能搜索到 匹配数加1 ans++; } return ans; } bool checkr(int x, int y) { bool wall = false, space = false; if (y == 0) return false; if (mpp[x][y-1] == 'X') wall = true; for (int i=y-2; i>=0; --i) { if (mpp[x][i] == '.') space = true; } if (wall && space) { for (int i=y; i<n; ++i) { p[x][i].x = maxr+1; // cout << x << "+++++" << i << "@" << maxr << endl; } return true; } return false; } bool checkc(int x, int y) { bool wall = false, space = false; if (x == 0) return false; if (mpp[x-1][y] == 'X') wall = true; for (int i=x-2; i>=0; --i) { if (mpp[i][y] == '.') space = true; } if (wall && space) { for (int i=x; i<n; ++i) { p[i][y].y = maxc+1; } return true; } return false; } int main() { while(~scanf("%d", &n) && n) { for (int i=0; i<n; ++i) { scanf("%s", mpp[i]); } //build mp memset(mp, 0, sizeof(mp)); for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) { p[i][j].x = i+1; p[i][j].y = j+1; } } maxr = n, maxc = n; for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) { if (mpp[i][j] == 'X') continue; if (checkr(i, j)) { // need to be divided 1.hava wall 2.have space 3.it is the first one maxr++; } if (checkc(i, j)) { maxc++; } } } int tot = n; for (int i=0; i<tot; ++i) { for (int j=0; j<tot; ++j) { if (mpp[i][j] == 'X') continue; int x = p[i][j].x; int y = p[i][j].y; mp[x][y]++; } } //build mp end // find the max match int ans = match(); printf("%d ", ans); } return 0; } /* 4 ..X. X... ..XX .X.. */
J：HDU 3395 Special Fish
Km求最优匹配简单题
代码：
#include <stdio.h> #include <string.h> #include <iostream> #define siz 110 #define inf 100000000 using namespace std; int lx[siz], ly[siz]; // 可行顶标集合 int slack[siz]; int visx[siz], visy[siz]; int mp[siz][siz]; // 边的集合 int link[siz]; // 匹配集合 int n, nx, ny; // 点的个数 左集合点的个数 和右集合点的个数 int val[siz]; char rel[siz][siz]; bool dfs(int x) { visx[x] = 1; // 左集合访问到的点一定都在交错树中------------- for (int i=1; i<=ny; ++i) { if (visy[i]) continue; int w = lx[x] + ly[i] - mp[x][i]; if (w == 0) { visy[i] = 1; // 右集合的点在相等子图中 就一定在交错树中------------ if (link[i] == -1 || dfs(link[i])) { link[i] = x; return 1; } } else slack[i] = min(slack[i], w); // 修改不在相等子图中的点 的slack值 } return 0; } int km() { memset(link, -1, sizeof(link)); // lx 和 ly的初始化 memset(ly, 0, sizeof(ly)); for (int i=1; i<=nx; ++i) { lx[i] = -inf; for (int j=1; j<=ny; ++j) { lx[i] = max(lx[i], mp[i][j]); } } // 从x集合的每个点寻找增广路 for (int x=1; x<=nx; ++x) { for (int i=1; i<=ny; ++i) { //slack 的初始化对当前点寻找增广路的左右过程中有效----------- slack[i] = inf; } //cout << x << "=== "; while(1) { memset(visx, 0, sizeof(visx)); //每次寻找增广路之前初始化---------- memset(visy, 0, sizeof(visy)); if (dfs(x)) break; //该点增广完成 // 否则修改可行顶标 int d = inf; for (int i=1; i<=ny; ++i) { if (!visy[i]) d = min(d, slack[i]); } for (int i=1; i<=nx; ++i) { if (visx[i]) lx[i] -= d; } for (int i=1; i<=ny; ++i) { if (visy[i]) ly[i] += d; else slack[i] -= d; } } } int res = 0; for (int i=1; i<=ny; ++i) { //必定已经找到一个所有相等子图的点导出的完美匹配--------- if (link[i] != -1) res += mp[link[i]][i]; // 右集合i的匹配点link[i] 这里不像无向图那样，需要注意顺序--------- } return res; } int main() { while (cin >> n && n) { memset(mp, 0, sizeof(mp)); nx = n, ny = n; for (int i=1; i<=n; ++i) { cin >> val[i]; } for (int i=0; i<n; ++i) { cin >> rel[i]; } for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) { int temp = rel[i][j] - '0'; if (temp == 1) { int w = val[i+1] ^ val[j+1]; mp[i+1][j+1] = w; } } } int ans = km(); cout << ans << endl; } return 0; }