題意

給定m個長度為n的01串（*既表示0 or 1。如*01表示001和101）。現在要把這些串都刪除掉，刪除的方法是：①一次刪除任意指定的一個；②如果有兩個串僅有一個字符不同，則可以同時刪除這兩個。求最少要多少次可以刪完，并且同一個串不能刪兩次。

思路

我們用點表示一個串，如果兩個串之間只有一個字符不同，那么這兩個串之間連接一條，最大匹配數就是節省的次數。 因為每個串中的1為奇數的串之間是不能匹配的（不可能只有1個不同），同理，偶數也是。所以，可以按照1的奇偶性把數據分成2份，所以是一個二分圖匹配。然后答案就是所有串數 - 最大匹配數。

代碼

? #include #include #include #include #include #include #define MID(x,y) ((x+y)/2) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int MAXV = 2005; //N1+N2 vector adj[MAXV]; struct MaximumMatchingOfBipartiteGraph{int vn;void init(int n){ //二分圖兩點集點的個數vn = n;for (int i = 0; i <= vn; i ++) adj[i].clear();}void add_uedge(int u, int v){adj[u].push_back(v);adj[v].push_back(u);}bool vis[MAXV];int mat[MAXV]; //記錄已匹配點的對應點bool cross_path(int u){for (int i = 0; i < (int)adj[u].size(); i ++){int v = adj[u][i];if (!vis[v]){vis[v] = true;if (mat[v] == 0 || cross_path(mat[v])){mat[v] = u;mat[u] = v;return true;}}}return false;}int hungary(){mem(mat, 0);int match_num = 0;for (int i = 1; i <= vn; i ++){mem(vis, 0);if (!mat[i] && cross_path(i)){match_num ++;}}return match_num;}void print_edge(){for (int i = 1; i <= vn; i ++){for (int j = 0; j < (int)adj[i].size(); j ++){printf("u = %d v = %d\n", i, adj[i][j]);}}} }match;vector s; int main(){//freopen("test.in", "r", stdin);//freopen("test.out", "w", stdout);int n, m;while(scanf("%d %d", &n, &m), n+m){getchar();s.clear();for (int i = 1; i <= m; i ++){char tmps[15];scanf("%s", tmps);int star = -1;for (int j = 0; j < n; j ++){if (tmps[j] == '*'){star = j;break;}}if (star == -1){if (find(s.begin(), s.end(), tmps) == s.end())s.push_back(string(tmps));}else{tmps[star] = '0';if (find(s.begin(), s.end(), tmps) == s.end())s.push_back(string(tmps));tmps[star] = '1';if (find(s.begin(), s.end(), tmps) == s.end())s.push_back(string(tmps));}}match.init(s.size());for (int i = 0; i < s.size(); i ++){for (int j = 0; j < i; j ++){int dif = 0;for (int k = 0; k < n; k ++){if (s[i][k] != s[j][k]){dif ++;if (dif > 1)break;}}if (dif == 1){match.add_uedge(j+1, i+1);}}}printf("%d\n", s.size() - match.hungary());}return 0; }

轉載于:https://www.cnblogs.com/AbandonZHANG/p/4114077.html

總結

以上是生活随笔為你收集整理的POJ 2724 Purifying Machine (二分图匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。