| ||||||||||
| 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 | |||||||||
题目的意思是,输出所有能够唯一确定匹配的pair。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator