poj 3020 一般圖最大匹配 帶花樹開花算法

poj 3020 一般圖最大匹配 帶花樹開花算法

poj 3020 一般圖最大匹配 帶花樹開花算法
題意：
給出一個h*w的圖，每個點都是'o'或'*'，最少要用多少個1*2的矩形才能把圖中所有的'*'都覆蓋掉。

限制：
1 <= h <= 40; 1 <= w <= 10

思路：
最小邊覆蓋=|V|-最大匹配
一般圖最大匹配，帶花樹開花算法

 

/*poj 3020 一般圖最大匹配 帶花樹開花算法
  題意：
  給出一個h*w的圖，每個點都是'o'或'*'，最少要用多少個1*2的矩形才能把圖中所有的'*'都覆蓋掉。
  限制：
  1 <= h <= 40; 1 <= w <= 10
  思路：
  最小邊覆蓋=|V|-最大匹配
  一般圖最大匹配，帶花樹開花算法
 */
#include 
#include 
#include 
#include 
using namespace std;

const int MAX_V = 405;

// 並查集維護
int fa[MAX_V];
int getFa(int x) { 
	return fa[x] == x ? x : fa[x] = getFa(fa[x]);
}
void merge(int a, int b) {
	a = getFa(a);
	b = getFa(b);
	if (a != b) fa[a] = b;
}

int V, match[MAX_V];
vector e[MAX_V];
int Q[MAX_V], rear;
int next[MAX_V], mark[MAX_V], vis[MAX_V];

// 樸素算法求某階段中搜索樹上兩點x, y的最近公共祖先r
int LCA(int x, int y) {
	static int t = 0; t++;
	while (true) {
		if (x != -1) {
			x = getFa(x); // 點要對應到對應的花上去
			if (vis[x] == t) return x;
			vis[x] = t;
			if (match[x] != -1) x = next[match[x]];
			else x = -1;
		}
		swap(x, y);
	}
}

void group(int a, int p) {
	while (a != p) {
		int b = match[a], c = next[b];

		// next數組是用來標記花朵中的路徑的，綜合match數組來用，實際上形成了
		// 雙向鏈表，如(x, y)是匹配的，next[x]和next[y]就可以指兩個方向了。
		if (getFa(c) != p) next[c] = b;

		// 奇環中的點都有機會向環外找到匹配，所以都要標記成S型點加到隊列中去，
		// 因環內的匹配數已飽和，因此這些點最多只允許匹配成功一個點，在aug中
		// 每次匹配到一個點就break終止了當前階段的搜索，並且下階段的標記是重
		// 新來過的，這樣做就是為了保證這一點。
		if (mark[b] == 2) mark[Q[rear++] = b] = 1;
		if (mark[c] == 2) mark[Q[rear++] = c] = 1;

		merge(a, b); merge(b, c);
		a = c;
	}
}

// 增廣
void aug(int s) {
	for (int i = 0; i < V; i++) // 每個階段都要重新標記
		next[i] = -1, fa[i] = i, mark[i] = 0, vis[i] = -1;
	mark[s] = 1;
	Q[0] = s; rear = 1; 
	for (int front = 0; match[s] == -1 && front < rear; front++) {
		int x = Q[front]; // 隊列Q中的點都是S型的
		for (int i = 0; i < (int)e[x].size(); i++) {
			int y = e[x][i];
			if (match[x] == y) continue; // x與y已匹配，忽略
			if (getFa(x) == getFa(y)) continue; // x與y同在一朵花，忽略
			if (mark[y] == 2) continue; // y是T型點，忽略
			if (mark[y] == 1) { // y是S型點，奇環縮點
				int r = LCA(x, y); // r為從i和j到s的路徑上的第一個公共節點
				if (getFa(x) != r) next[x] = y; // r和x不在同一個花朵，next標記花朵內路徑
				if (getFa(y) != r) next[y] = x; // r和y不在同一個花朵，next標記花朵內路徑

				// 將整個r -- x - y --- r的奇環縮成點，r作為這個環的標記節點，相當於論文中的超級節點
				group(x, r); // 縮路徑r --- x為點
				group(y, r); // 縮路徑r --- y為點
			}
			else if (match[y] == -1) { // y自由，可以增廣，R12規則處理
				next[y] = x;
				for (int u = y; u != -1; ) { // 交叉鏈取反
					int v = next[u];
					int mv = match[v];
					match[v] = u, match[u] = v;
					u = mv;
				}
				break; // 搜索成功，退出循環將進入下一階段
			}
			else { // 當前搜索的交叉鏈+y+match[y]形成新的交叉鏈，將match[y]加入隊列作為待搜節點
				next[y] = x;
				mark[Q[rear++] = match[y]] = 1; // match[y]也是S型的
				mark[y] = 2; // y標記成T型
			}
		}
	}
}

bool g[MAX_V][MAX_V];
const int N=45;
char str[N][N];
int mp[N][N];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

int h,w;
bool ok(int x,int y){
	if(x>=0 && x=0 && y