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