Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个c++代码

Posted by a280920481 at 2018-12-05 22:33:03 on Problem 2226
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator