二分图性质以及求解算法

学习资料：传送门

匈牙利算法通俗介绍：传送门

交叉染色法判断二分图：传送门

Hopcroft-Karp算法：传送门

 另一种讲解：传送门

KM算法求二分匹配的最大权问题：传送门

加深理解：传送门

HDU2444

题意：首先问是否是一个二分图， 然后求最大匹配

先用交叉染色法判断一下是否是二分图， 然后用匈牙利算法求出最大匹配，代码写的很丑....

#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <set> using namespace std; #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 205; set<int> s1, s2; short int vis[qq]; int gra[qq][qq]; int match[qq]; bool ismat[qq]; int n, m; bool flag; void dfs(int u, int color){ vis[u] = color; for(int i = 1; i <= n; ++i){ if(gra[u][i]){ int v = i; if(vis[v] > 1){ if(vis[u] == vis[v]) flag = false; }else{ dfs(v, color == 2 ? 3 : 2); } } } } bool dfs(int u){ for(int i = 1; i <= n; ++i) if(gra[u][i] && !ismat[i]){ ismat[i] = true; if(match[i] == -1 || dfs(match[i])){ match[i] = u; return true; } } return false; } int main(){ int a, b; while(scanf("%d%d", &n, &m) != EOF){ memset(gra, 0, sizeof(gra)); memset(vis, 0, sizeof(vis)); memset(match, -1, sizeof(match)); memset(ismat, false, sizeof(ismat)); int a, b; REP(i, 0, m){ scanf("%d%d", &a, &b); gra[a][b] = gra[b][a] = 1; vis[a] = vis[b] = 1; } flag = true; for(int i = 1; i <= n; ++i) if(vis[i] == 1) dfs(i, 2); if(!flag){ puts("No"); continue; } int cnt = 0; for(int i = 1; i <= n; ++i) if(vis[i] == 2){ memset(ismat, false, sizeof(ismat)); if(dfs(i)) cnt++; } printf("%d\n", cnt); } return 0; }

HDU1281

最初我一直在向这组数据是怎么放的

4 4 2

1 2

1 4

最多就能放1一个车， 我一直以为能放两个。。。

苦苦不得其解、  最后才发现只是说棋盘中只有这些点可以放车， 并不代表没给出的点就是障碍

那么也就是说每一行就是放一个车， 同理每一列也一样

然后就是二分匹配去枚举即可

#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <vector> using namespace std; #define LL long long #define pb push_back int n, m, k; int gra[105][105]; bool visitd[105]; int x[10005], y[10005]; int link[105]; int Dfs(int u){ for(int i = 1; i <= m; ++i) if(!visitd[i] && gra[u][i]){ visitd[i] = true; if(link[i] == -1 || Dfs(link[i])){ link[i] = u; return true; } } return false; } int Maxmatch(){ int t = 0; for(int i = 1; i <= n; ++i){ memset(visitd, false, sizeof(visitd)); if(Dfs(i)) t++; } return t; } int main(){ int c = 1; while(scanf("%d%d%d", &n, &m, &k) != EOF){ memset(gra, 0, sizeof(gra)); memset(link, -1, sizeof(link)); for(int i = 0; i < k; ++i){ scanf("%d%d", &x[i], &y[i]); gra[x[i]][y[i]] = 1; } int t = 0; int num = Maxmatch(); for(int i = 0; i < k; ++i){ memset(link, -1, sizeof(link)); gra[x[i]][y[i]] = 0; int d = Maxmatch(); gra[x[i]][y[i]] = 1; if(d != num) t++; } printf("Board %d have %d important blanks for %d chessmen.\n", c++, t, num); } return 0; }

HDU2819

题意：可以任意交换两行或者两列，使得最后的对角线要全是1

这题真的运用到线性代数的内容， 对角线能不能全是1， 就是看矩阵的秩能否为n， 假设最终能化成对角线全是1， 那么我们任意交换两行或者两列，这样的图形实际上保证了每一行有一个对应的列， 这行和这列中只存在一个1。

线性代数的知识是如果不能通过矩阵初等变换行变换使得最后对角线元素都不为0， 那么矩阵初等变换的列变换也不能达到要求，同理两种变换混合也不行（一般矩阵初等边变换等价于行变换或者列变换）

那么结果很明显， 就是对所有1的x轴和y轴进行二分图匹配，然后找路径即可。

#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <vector> using namespace std; #define REP(i, x, n) for(int i = x; i <= n; ++i) const int qq = 105; int match[qq]; int gra[qq][qq]; bool used[qq]; int n; int a[1005], b[1005]; bool Dfs(int u){ REP(i, 1, n) if(gra[u][i] && !used[i]){ used[i] = true; if(match[i] == -1 || Dfs(match[i])){ match[i] = u; return true; } } return false; } void Init(){ memset(gra, 0, sizeof(gra)); memset(match, -1, sizeof(match)); } int main(){ while(scanf("%d", &n) != EOF){ Init(); REP(i, 1, n) REP(j, 1, n){ scanf("%d", &gra[i][j]); } int res = 0; for(int i = 1; i <= n; ++i){ memset(used, false, sizeof(used)); if(Dfs(i)) res++; } if(res < n){ puts("-1"); continue; } // for(int i = 1; i <= n; ++i) // printf("%d \n", match[i]); int tot = 0; for(int i = 1; i <= n; ++i){ if(match[i] != i){ a[tot] = i; b[tot] = match[i]; for(int j = 1; j <= n; ++j){ if(match[j] == i) match[j] = match[i]; } match[i] = i; tot++; } } printf("%d\n", tot); for(int i = 0; i < tot - 1; ++i) printf("R %d %d\n", a[i], b[i]); if(tot != 0) printf("R %d %d\n", a[tot - 1], b[tot - 1]); } return 0; }

HDU2389

题意：Time分钟后下雨， 给出n个人的位置和时间以及m把伞的位置， 一把伞只能配一个人，问最多有多少个人能拿到伞。

数据范围有点大、试了一发普通的匈牙利算法直接T， 要用到时间复杂度为O（n^0.5 * m）的Hopcroft-Carp算法

#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; #define LL long long #define pb push_back #define mst(Arr, x) memset(Arr, x, sizeof(Arr)) #define REP(i, x, n) for(int i = x; i < n; ++i) const int MAXN = 3005; const int MAXM = 3005 * 3005; const int INF = 0x3f3f3f3f; struct Edge{ int v, next; }edge[MAXM]; struct node{ double x, y; double v; }a[MAXN], b[MAXN]; int nx, ny; int cnt, t, dis; int head[MAXN]; int xlink[MAXN], ylink[MAXN]; int dx[MAXN], dy[MAXN]; bool vis[MAXN]; void Init(){ cnt = 0; mst(head, -1); mst(xlink, -1); mst(ylink, -1); } void Read_graph(int u, int v){ edge[cnt].v = v; edge[cnt].next = head[u], head[u] = cnt++; } int Bfs(){ queue<int> q; dis = INF; mst(dx, -1); mst(dy, -1); for(int i = 0; i < nx; ++i) if(xlink[i] == -1){ q.push(i); dx[i] = 0; } while(!q.empty()){ int u = q.front(); q.pop(); if(dx[u] > dis) break; for(int e = head[u]; e != -1; e = edge[e].next){ int v = edge[e].v; if(dy[v] == -1){ dy[v] = dx[u] + 1; if(ylink[v] == -1){ dis = dy[v]; }else{ dx[ylink[v]] = dy[v] + 1; q.push(ylink[v]); } } } } return dis != INF; } int Find(int u){ for(int e = head[u]; e != -1; e = edge[e].next){ int v = edge[e].v; if(!vis[v] && dy[v] == dx[u] + 1){ vis[v] = 1; if(ylink[v] != -1 && dy[v] == dis) continue; if(ylink[v] == -1 || Find(ylink[v])){ xlink[u] = v, ylink[v] = u; return 1; } } } return 0; } int MaxMatch(){ int ans = 0; while(Bfs()){ mst(vis, 0); for(int i = 0; i < nx; ++i) if(xlink[i] == -1){ ans += Find(i); } } return ans; } double dist(const node a, const node b){ return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } void read_case(){ Init(); int Time; scanf("%d", &Time); scanf("%d", &nx); for(int i = 0; i < nx; ++i){ scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].v); } scanf("%d", &ny); for(int i = 0; i < ny; ++i){ scanf("%lf%lf", &b[i].x, &b[i].y); for(int j = 0; j < nx; ++j){ double limit = a[j].v * Time; double s = dist(a[j], b[i]); if(s <= limit) Read_graph(j, i); } } } void solve(){ read_case(); int ans = MaxMatch(); printf("%d\n\n", ans); } int main(){ int T, times = 0; scanf("%d", &T); while(T--){ printf("Scenario #%d:\n", ++times); solve(); } return 0; }

HDU3829

题意：n只猫，m只狗， 有p个小朋友，每一个小朋友必定会喜欢其中一只猫或者狗，也必定会讨厌某只猫或狗（如果喜欢的是猫讨厌的必定是狗反之亦然），现在要移除一些动物，对于一个小朋友如果他喜欢的动物留下来了并且讨厌的动物被移除了，那么他就会开心，现在要移除一些动物使得开心的孩子最多。

最开始一直在着眼于猫和狗之间建图，发现根本毫无作用， 最后发现小朋友之间是存在矛盾关系的，比如小朋友a喜欢某个动物，但是小朋友b刚好不喜欢那个动物，这样a b小朋友之间就存在一种矛盾关系， 这种情况下肯定只能选择一个小朋友让他开心， 这样就形成了一张二分图， 答案就是二分图的最大独立集。

#include <cstring> #include <cmath> #include <cstdio> #include <cmath> #include <iostream> #include <algorithm> #include <vector> using namespace std; #define LL long long #define pb push_back #define mst(Arr, x) memset(Arr, x, sizeof(Arr)) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 505; const int FG = 101; int gra[qq][qq], match[qq]; bool vis[qq]; int n, m, p; vector<int> like[qq], dislike[qq]; void Read(int id, int flag){ char op[25]; scanf("%s", op); int num = 0; for(int i = 1; i < strlen(op); ++i) num = num * 10 + op[i] - '0'; if(op[0] == 'C'){ if(!flag) like[num].pb(id); else dislike[num].pb(id); }else{ if(!flag) like[num + n].pb(id); else dislike[num + n].pb(id); } } bool Dfs(int u){ for(int i = 0; i < p; ++i)if(gra[u][i] && !vis[i]){ vis[i] = true; if(match[i] == -1 || Dfs(match[i])){ match[i] = u; match[u] = i; return true; } } return false; } void Init(){ mst(gra, 0); mst(match, -1); for(int i = 0; i <= n + m; ++i) like[i].clear(), dislike[i].clear(); } int main(){ while(scanf("%d%d%d", &n, &m, &p) != EOF){ Init(); REP(i, 0, p){ Read(i, 0), Read(i, 1); } for(int i = 1; i <= n + m; ++i){ int Lk = (int)like[i].size(); int Dk = (int)dislike[i].size(); for(int j = 0; j < Lk; ++j) for(int k = 0; k < Dk; ++k) gra[like[i][j]][dislike[i][k]] = gra[dislike[i][k]][like[i][j]] = 1; } int ans = 0; for(int i = 0; i < p; ++i){ if(match[i] == -1){ mst(vis, false); if(Dfs(i)) ans++; } } printf("%d\n", p - ans); } return 0; }

HDU2255

KM算法求二分图最大权和问题

#include <cstdio> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> using namespace std; #define LL long long #define pb push_back #define mst(Arr, x) memset(Arr, x, sizeof(Arr)) #define REP(i, x, n) for(int i = x; i < n; ++i) const int qq = 305; const int INF = 2147483647; int w[qq][qq], match[qq], visx[qq], visy[qq], lx[qq], ly[qq]; int lack, n, m; bool Find(int x){ visx[x] = true; for(int y = 0; y < n; ++y){ if(visy[y]) continue; int t = lx[x] + ly[y] - w[x][y]; if(!t){ visy[y] = true; if(!~match[y] || Find(match[y])){ match[y] = x; return true; } }else{ lack = min(lack, t); } } return false; } int Km(){ mst(match, -1); for(int j, i = 0; i < n; ++i){ lx[i] = w[i][0]; ly[i] = 0; for(j = 1; j < n; ++j) lx[i] = max(lx[i], w[i][j]); } mst(match, -1); for(int x = 0; x < n; ++x) while(true){ mst(visx, 0); mst(visy, 0); lack = INF; if(Find(x)) break; for(int i = 0; i < n; ++i){ if(visx[i]) lx[i] -= lack; if(visy[i]) ly[i] += lack; } } int sum = 0; for(int i = 0; i < n; ++i) sum += w[match[i]][i]; return sum; } int main(){ while(scanf("%d", &n) != EOF){ for(int j, i = 0; i < n; ++i) for(j = 0; j < n; ++j) scanf("%d", &w[i][j]); Km(); int sum = Km(); printf("%d\n", sum); } return 0; }

注意w[][]数组赋值界限，有可能在lx[x] + ly[y]  - w[x][y]中溢出