poj 1486二分図最大マッチング必須エッジ
題意:点と矩形の最大マッチングを求めることです.このような唯一の対応関係があれば出力し,なければnoneを出力する.
考え方:点とマトリクスを接続し、最大マッチングを求めます.同時にエッジを削除するテクニックに注意します.
考え方:点とマトリクスを接続し、最大マッチングを求めます.同時にエッジを削除するテクニックに注意します.
#include
#include
using namespace std;
struct point
{
int x,y;
}P[100];
struct rec
{
int minx;
int miny;
int maxx;
int maxy;
}R[100];
bool g[100][100];
bool vis[100];
int link[100];
int N;
bool check(int i,int j)
{
int xx=P[i].x;
int yy=P[i].y;
if(xx>R[j].minx&&xxR[j].miny&&yy