本文共 4189 字，大约阅读时间需要 13 分钟。
无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 using namespace std; 15 #define INT_MAX 10000000 16 #define N 1005 17 #define CLR(arr, what) memset(arr, what, sizeof(arr)) 18 int capacity[N][N]; //容量 19 int flow[N]; //残余流量 20 int pre[N]; //前趋 21 int n; //节点个数 22 23 queue Q; 24 25 int BFS(int src, int des) { 26 //初始化 27 while (!Q.empty()) { 28 Q.pop(); 29 } 30 for (int i = 1; i < n + 1; i++) { 31 pre[i] = -1; 32 } 33 pre[src] = 0; 34 flow[src] = INT_MAX; //初始化源点的流量为无穷大 35 Q.push(src); 36 while (!Q.empty()) { 37 int index = Q.front(); 38 Q.pop(); 39 if (index == des) { //找到了增广路径 40 break; 41 } 42 for (int i = 1; i < n + 1; i++) { 43 if (i != src && capacity[index][i] > 0 && pre[i] == -1) { 44 pre[i] = index; 45 //增广路残容流量 46 flow[i] = min(capacity[index][i], flow[index]); 47 Q.push(i); 48 } 49 } 50 } //while 51 if (pre[des] == -1) { 52 return -1; //残留图中不存在增广路径 53 } else { 54 return flow[des]; 55 } 56 } 57 58 int MaxFlow(int src, int des) { 59 int aug = 0; 60 int sumflow = 0; 61 while ((aug = BFS(src, des)) != -1) { 62 int k = des; //利用前驱寻找路径 63 while (k != src) { 64 int last = pre[k]; 65 capacity[last][k] -= aug; 66 capacity[k][last] += aug; 67 k = last; 68 } 69 sumflow += aug; 70 } 71 return sumflow; 72 } 73 struct node { 74 string in, out; 75 int cap; 76 }; 77 int checkin(string & a, string& b) { 78 int sz = a.size(); 79 bool judge = 1; 80 for (int i = 0; i < sz; i++) { 81 if (a[i] == '2' || b[i] == '2') { 82 continue; 83 } else if (a[i] != b[i]) { 84 judge = 0; 85 break; 86 } 87 } 88 if (1 == judge) 89 return 1; 90 return 0; 91 } 92 93 int cur[N]; //后继 94 int dis[N]; //距离 95 int gap[N]; //层结点数（用于间隙优化） 96 int SAP(int s, int t) //源点、汇点、结点数 97 { 98 CLR(gap, 0); 99 CLR(cur, 0);100 CLR(dis, 0);101 int u = pre[s] = s, maxflow = 0, aug = INT_MAX;102 int v;103 gap[0] = n;104 while (dis[s] < n) {105 bool flag = false;106 for (v = cur[u]; v <= n; ++v) //寻找允许弧107 {108 if (capacity[u][v] > 0 && dis[u] == dis[v] + 1) {109 flag = true;110 break;111 }112 }113 if (flag) //找到允许弧114 {115 pre[v] = u;116 cur[u] = v;117 aug = min(aug, capacity[u][v]);118 u = v;119 if (v == t) //找到完整增广路120 {121 maxflow += aug;122 for (v = t; v != s; v = pre[v]) //更新残留网络123 {124 capacity[pre[v]][v] -= aug; //正向边125 capacity[v][pre[v]] += aug; //反向边126 }127 aug = INT_MAX;128 u = s; //重新从源点寻找129 }130 } else //找不到允许弧131 {132 int mindis = n;133 for (v = 1; v <= n; ++v) //重新标号134 {135 if (capacity[u][v] && mindis > dis[v]) {136 cur[u] = v;137 mindis = dis[v];138 }139 }140 if (--gap[dis[u]] == 0) //更新断层 + 判断是否断层（间隙优化）141 break;142 gap[dis[u] = mindis + 1]++; //更新断层143 u = pre[u]; //当前弧优化144 }145 }146 return maxflow;147 }148 149 inline void addedge(int x, int y, int c) { // add an arc(x -> y, c); vertex: 0 ~ n-1;150 capacity[x][y] = c;151 }152 int tag[N][N]; //容量153 int dx[] = { 1, 0, -1, 0 };154 int dy[] = { 0, 1, 0, -1 };155 int main() {156 int u, v, r, c, itnu;157 cin >> itnu;158 for (int abc = 0; abc < itnu; abc++) {159 CLR(capacity, 0);160 CLR(tag, 0);161 string tmp;162 vector data;163 cin >> r >> c;164 for (int i = 0; i < r; i++) {165 cin >> tmp;166 data.push_back(tmp);167 }168 int node_num = 0;169 for (int i = 0; i < r; i++) {170 for (int j = 0; j < c; j++) {171 if (data[i][j] == '*') {172 node_num++;173 tag[i][j] = node_num;174 }175 }176 }177 n = node_num * 2 + 2;178 for (int i = 0; i < node_num; i++) {179 addedge(0, i + 1, 1);180 addedge(node_num + i + 1, n - 1, 1);181 }182 for (int i = 0; i < r; i++) {183 for (int j = 0; j < c; j++) {184 if (tag[i][j] != 0) {185 u = tag[i][j];186 for (int a = 0; a < 4; a++) {187 int x = i + dx[a];188 int y = j + dy[a];189 if (x >= 0 && x < r && y >= 0 && y < c) {190 if (tag[x][y] > 0) {191 v = tag[x][y] + node_num;192 addedge(u, v, 1);193 }194 }195 }196 }197 }198 }199 // int sum = MaxFlow(0, n - 1);200 int sum = SAP( 0, n - 1);201 cout << node_num - sum / 2 << endl;202 }203 return 0;204 }
转载于:https://www.cnblogs.com/kakamilan/archive/2013/05/11/3072588.html