Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴个c++代码#include <iostream> using namespace std; int G[2501][1250];//邻接表 int deg[2501];//每个节点的度 int match[2501];//与节点配对的节点 bool used[1251];//记录节点是否已被搜索过 int F[51][51];//记录与 (i, j) 相连的纵向节点 void add_edge(int u, int w); bool dfs(int v); int main() { int R, C, rp, cp = 0, ans = 0;// rp cp 分别是横向和纵向的节点数 char ch; cin >> R >> C; for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { cin >> ch; if (ch == '*') { if (!F[i][j - 1]) { cp++; } F[i][j] = cp; } } } rp = cp; for (int j = 1; j <= C; j++) { for (int i = 1; i <= R; i++) { if (F[i][j]) { if (!F[i - 1][j]) { rp++; } add_edge(F[i][j], rp); } } } for (int i = 1; i <= cp; i++) { for (int j = 1; j <= cp; j++) { used[j] = false; } if (dfs(i)) { ans++; } } cout << ans << '\n'; return 0; } void add_edge(int u, int w) { G[u][deg[u]++] = w; G[w][deg[w]++] = u; return; } bool dfs(int v) { int u, w; used[v] = true; for (int i = 0; i < deg[v]; i++) { u = G[v][i]; w = match[u]; if (!w) { match[v] = u; match[u] = v; return true; } else if (!used[w]) { if (dfs(w)) { match[v] = u; match[u] = v; return true; } } } return false; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator