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

题目的意思是,输出所有能够唯一确定匹配的pair。

Posted by a280920481 at 2019-02-27 17:25:51 on Problem 1486 and last updated at 2019-02-27 17:26:19
#include <iostream>
#include <string.h>
using namespace std;


const int MAX_N = 30;
const int MAX_V = MAX_N << 1;

struct Rect
{
	int x[2];
	int y[2];
}R[MAX_V];
bool inrect(const int & x, const int & y, const Rect & r);


int G[MAX_V][MAX_V];
int deg[MAX_V];
int V;
int match[MAX_V];
bool used[MAX_V];

void add_edge(int u, int v);
bool dfs(int v);
int bipartite_matching();

int binmatch[MAX_V];
bool can[MAX_N][MAX_N];

int unimatch[MAX_N];

int main()
{
	int n, x, y, T = 0;

	while (++T)
	{
		scanf("%d", &n);
		if (!n)
		{
			break;
		}
		memset(deg, 0, sizeof(deg));
		memset(can, 0, sizeof(can));

		for (int i = 0; i < n; i++)
		{
			scanf("%d%d%d%d", R[i].x, R[i].x + 1, R[i].y, R[i].y + 1);
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d", &x, &y);

			for (int j = 0; j < n; j++)
			{
				if (inrect(x, y, R[j]))
				{
					can[i][j] = true;
					add_edge(j, n + i);
				}
		
			}
		}

		V = n << 1;
		int b = bipartite_matching() - 1;
		int ans = 0;

		for (int i = 0; i < n; i++)
		{
			binmatch[i] = match[i] - n;	
		}
		for (int k = 0; k < n; k++)
		{
			memset(deg, 0, sizeof(deg));
			can[binmatch[k]][k] = false;
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (can[i][j])
					{
						add_edge(j, n + i);
					}
				}
			}
			int b2 = bipartite_matching();
			if (b2 == b)
			{
				unimatch[ans++] = k;
			}
			can[binmatch[k]][k] = true;
		}
		
		if (ans)
		{
			printf("Heap %d\n(%c,%d)", T, (char)(unimatch[0] + 'A'), binmatch[unimatch[0]] + 1);
			for (int i = 1; i < ans; i++)
			{
				printf(" (%c,%d)", (char)(unimatch[i] + 'A'), binmatch[unimatch[i]] + 1);
			}
		}
		else
		{
			printf("Heap %d\nnone", T);
		}
		printf("\n\n");
	}


	return 0;
}

bool inrect(const int & x, const int & y, const Rect & r)
{
	return x >= r.x[0]
		&& x <= r.x[1]
		&& y >= r.y[0]
		&& y <= r.y[1];
}

void add_edge(int u, int v)
{
	G[u][deg[u]++] = v;
	G[v][deg[v]++] = u;
}

bool dfs(int v)
{
	used[v] = true;
	for (int i = 0; i < deg[v]; i++)
	{
		int u = G[v][i];
		int w = match[u];

		if (w == -1 || !used[w] && dfs(w))
		{
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

int bipartite_matching()
{
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int v = 0; v < V; v++)
	{
		if (match[v] == -1)
		{
			memset(used, 0, sizeof(used));
			if (dfs(v))
			{
				res++;
			}
		}
	}
	return res;
}

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