首页 > 代码库 > UVa1663 Purifying Machine (二分图最大匹配,最大流)
UVa1663 Purifying Machine (二分图最大匹配,最大流)
链接：http://vjudge.net/problem/UVA-1663
分析：先把原来m个模板串取出来扔进set里去重，然后将去重后的匹配串从1~cnt编号。题目说每个模板串最多一个星号“*”，所以说一个匹配串只有唯一的一个跟它只有一个位上的数字不同的另一个匹配串组合成一个模板串，这就成了二分图最大匹配问题了。然后针对每个匹配串找出和它只有一位数字不同的其它匹配串，把其编号存进数组vector<int> e[i]里。然后对cnt个匹配串以e[i][j]为状态转移进行dfs黑白染色，这样就把这些匹配串分成了左右两列，同一列中的匹配串至少也有两个位上的数字不同不可能组合成一个模板串，满足二分图的要求，然后从源点s向白色结点连一条容量为1的弧，从黑色结点向汇点t连一条容量为1的弧，对于白色结点所能匹配的所有黑色结点，都连一条容量为1的弧。跑一个s-t的最大流，得到匹配对数。再用cnt减去匹配对数即为答案。
1 #include <iostream> 2 #include <string> 3 #include <set> 4 #include <queue> 5 #include <cstring> 6 #include <vector> 7 using namespace std; 8 9 const int maxn = 1000 + 5; 10 const int INF = 0x3f3f3f3f; 11 12 struct Edge { 13 int from, to, cap, flow; 14 Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {} 15 }; 16 17 struct EdmondsKarp { 18 int n, m; 19 vector<Edge> edges; 20 vector<int> G[maxn]; 21 int a[maxn]; 22 int p[maxn]; 23 24 void init(int n) { 25 for (int i = 0; i < n; i++) G[i].clear(); 26 edges.clear(); 27 } 28 29 void AddEdge(int from, int to, int cap) { 30 edges.push_back(Edge(from, to, cap, 0)); 31 edges.push_back(Edge(to, from, 0, 0)); 32 m = edges.size(); 33 G[from].push_back(m - 2); 34 G[to].push_back(m - 1); 35 } 36 37 int Maxflow(int s, int t) { 38 int flow = 0; 39 for (;;) { 40 memset(a, 0, sizeof(a)); 41 queue<int> Q; 42 Q.push(s); 43 a[s] = INF; 44 while (!Q.empty()) { 45 int x = Q.front(); Q.pop(); 46 for (int i = 0; i < G[x].size(); i++) { 47 Edge& e = edges[G[x][i]]; 48 if (!a[e.to] && e.cap > e.flow) { 49 p[e.to] = G[x][i]; 50 a[e.to] = min(a[x], e.cap - e.flow); 51 Q.push(e.to); 52 } 53 } 54 if (a[t]) break; 55 } 56 if (!a[t]) break; 57 for (int u = t; u != s; u = edges[p[u]].from) { 58 edges[p[u]].flow += a[t]; 59 edges[p[u] ^ 1].flow -= a[t]; 60 } 61 flow += a[t]; 62 } 63 return flow; 64 } 65 }; 66 67 EdmondsKarp g; 68 69 int n, m; 70 string s[maxn]; 71 set<string> st; 72 vector<int> e[maxn * 2]; 73 int color[maxn]; 74 75 bool ismatch(string& a, string& b) { 76 int cnt = 0; 77 for (int i = 0; i < n; i++) 78 if (a[i] != b[i]) cnt++; 79 if (cnt == 1) return true; 80 else return false; 81 } 82 83 void AddColor(int s, int c) { 84 color[s] = c; 85 for (int i = 0; i < e[s].size(); i++) { 86 int t = e[s][i]; 87 if (!color[t]) AddColor(t, 3 - c); 88 } 89 } 90 91 int main() { 92 while (cin >> n >> m && (n || m)) { 93 for (int i = 0; i < m; i++) cin >> s[i]; 94 // for (int i = 0; i < m; i++) cout << s[i] << endl; 95 st.clear(); 96 for (int i = 0; i < m; i++) { 97 int j = 0; 98 while (j < n) { 99 if (s[i][j] == ‘*‘) {100 s[i][j] = ‘0‘;101 st.insert(s[i]);102 s[i][j] = ‘1‘;103 st.insert(s[i]);104 break;105 }106 j++;107 }108 if (j == n) st.insert(s[i]);109 }110 // cout << "ok" << endl;111 int cnt = 0;112 for (set<string>:: iterator it = st.begin(); it != st.end(); it++)113 s[++cnt] = *it;114 // for (int i = 1; i <= cnt; i++) cout << s[i] << endl;115 for (int i = 1; i <= cnt; i++) e[i].clear();116 for (int i = 1; i <= cnt; i++)117 for (int j = i + 1; j <= cnt; j++)118 if (ismatch(s[i], s[j])) {119 e[i].push_back(j);120 e[j].push_back(i);121 }122 memset(color, 0, sizeof(color));123 for (int i = 1; i <= cnt; i++) if (!color[i]) AddColor(i, 1);124 // for (int i = 1; i <= cnt; i++) cout << color[i] << endl;125 g.init(cnt + 2);126 for (int i = 1; i <= cnt; i++) {127 if (color[i] == 1) {128 g.AddEdge(0, i, 1);129 // g.AddEdge(i, 0, 0);130 for (int j = 0; j < e[i].size(); j++) {131 int v = e[i][j];132 g.AddEdge(i, v, 1);133 // g.AddEdge(v, i, 0);134 }135 }136 if (color[i] == 2) {137 g.AddEdge(i, cnt + 1, 1);138 // g.AddEdge(cnt + 1, i, 0);139 }140 }141 // cout << g.Maxflow(0, cnt + 1) << endl;142 cout << cnt - g.Maxflow(0, cnt + 1) << endl;143 }144 return 0;145 }
UVa1663 Purifying Machine (二分图最大匹配,最大流)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。