題意：
? ? ? 有n個矩形，每個矩形上的某個位置上都有一個點，但是由于矩形是透明的，當(dāng)一些矩形重疊在一起的時候就很可能分不清哪個點是那個矩形的，給你n個矩形的坐標(biāo)，還有n個點的坐標(biāo)，然后讓你找出所有能確定的點。


思路：
? ? ? ?兩種方法做的，第一種是用的模擬的方法，我是這么想的，如果把一個狀態(tài)給我們自己我們會怎么判斷？我肯定是先找到我一眼就能看出來的刪除，什么樣的算是可以刪除的？如果一個框上只有一個點，或者一個點只在一個框上，那么就可以肯定找到了一對，這樣做的話要考慮到一個問題，那么就是有對是一看看不出來的，也就是說一開始斷定不了，隨著一些可以斷定的刪除之后就可以斷定了，所以要while（1）循環(huán)的去找，這樣顯然是能搞定的，寫的時候可以存兩個方向的圖，還有度數(shù)...模擬細節(jié)不啰嗦，然后就是第二種方法，這個方法比較容易寫，也是大多數(shù)人認可的方法，但是一開始我并沒有寫，原因是我很難說服我自己這種方法是對的，因為我總擔(dān)心，如果當(dāng)前這條邊不是匹配的關(guān)鍵邊，但是隨著別的邊的刪除，后來不是匹配的有成了匹配的怎么辦？這么想可能是因為我寫的第一種方法while(1)的原因，后來就是不停的自己畫畫畫，終于明白了，哎！其實是我自己想多了，首先用匹配去做與我的第一種方法根本沒有任何關(guān)聯(lián)，也就是思路完全不同，匹配的思路就是只要是關(guān)鍵邊，那么刪除之后肯定是對匹配數(shù)有影響，如果沒有影響的邊，無論怎么while(1)最后還是沒有影響，因為至少出現(xiàn)一組可以和他替換的邊，這么這兩組（或多組）可以互相替換的邊彼此束縛著對方，就像是死鎖一樣，已經(jīng)死鎖的關(guān)聯(lián)進程中，無論你以什么樣的順序去嘗試執(zhí)行都沒意義，因為你“在環(huán)里了”,匹配的實現(xiàn)起來比較簡單，直接匹配一遍，然后嘗試刪除匹配好的邊就行了。
? ??


#include<stdio.h>
#include<string.h>
#include<algorithm>




#define N_node 26 + 5
#define N_edge 26 * 26 + 10


using namespace std;


typedef struct
{
? ? int to ,next;
}STAR;


typedef struct
{
? ? int x1 ,x2 ,y1 ,y2;
}EDGE;


typedef struct
{
? ? int x ,y;
}NODE;


typedef struct
{
? ? int id;
? ? char c;
}ANS;


ANS ans[N_node];
STAR E[N_edge];
EDGE edge[N_node];
NODE node[N_node];
int list[N_node] ,tot;
int mkdfs[N_node] ,mkgx[N_node];
int p1[N_node] ,p2[N_node];


void add(int a ,int b)
{
? ? E[++tot].to = b;
? ? E[tot].next = list[a];
? ? list[a] = tot;
}


int DFS_XYL(int x ,int a ,int b)
{
? ? for(int k = list[x] ;k ;k = E[k].next)
? ? {
? ? ? ? int to = E[k].to;
? ? ? ? if(x == a && b == to)
? ? ? ? continue;
? ? ? ? if(mkdfs[to]) continue;
? ? ? ? mkdfs[to] = 1;
? ? ? ? if(mkgx[to] == -1 || DFS_XYL(mkgx[to] ,a ,b))
? ? ? ? {
? ? ? ? ? ? mkgx[to] = x;
? ? ? ? ? ? return 1;
? ? ? ? }
? ? }
? ? return 0;
}


int XYL(int n ,int a ,int b)
{
? ? memset(mkgx ,255 ,sizeof(mkgx));
? ? int ans = 0;
? ? for(int i = 1 ;i <= n ;i ++)
? ? {
? ? ? ? memset(mkdfs ,0 ,sizeof(mkdfs));
? ? ? ? ans += DFS_XYL(i ,a ,b);
? ? }
? ? return ans;
}


bool jude(EDGE a ,NODE b)
{
? ? return a.x1 <= b.x && a.x2 >= b.x && a.y1 <= b.y && a.y2 >= b.y;
}


bool camp(ANS a ,ANS b)
{
? ? return a.c < b.c;
}


int main ()
{
? ? int n ,i ,j ,cas = 1;
? ? while(~scanf("%d" ,&n) && n)
? ? {
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%d %d %d %d" ,&edge[i].x1 ,&edge[i].x2 ,&edge[i].y1 ,&edge[i].y2);
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%d %d" ,&node[i].x ,&node[i].y);
? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? tot = 1;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? ? if(jude(edge[i] ,node[j]))
? ? ? ? add(i ,j);
? ? ? ? XYL(n ,0 ,0);
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? p1[i] = mkgx[i] ,p2[i] = i;
? ? ? ? int ansid = 0;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? if(XYL(n ,p1[i] ,p2[i]) != n)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ans[++ansid].c = p1[i] + 'A' - 1;
? ? ? ? ? ? ? ? ans[ansid].id = p2[i];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? printf("Heap %d\n" ,cas ++);
? ? ? ? if(!ansid) printf("none\n");
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? sort(ans + 1 ,ans + ansid + 1 ,camp);
? ? ? ? ? ? for(i = 1 ;i <= ansid ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(i == 1) printf("(%c,%d)" ,ans[i].c ,ans[i].id);
? ? ? ? ? ? ? ? else printf(" (%c,%d)" ,ans[i].c ,ans[i].id);
? ? ? ? ? ? }
? ? ? ? ? ? printf("\n");
? ? ? ? }
? ? ? ? printf("\n");
? ? }
}




















? ? ??
? ? ??




#include<stdio.h>
#include<string.h>
#include<algorithm>


#define N_node 26 + 5
#define N_edge 26 * 26 + 10


using namespace std;


typedef struct
{
? ? int to ,next;
}STAR;


typedef struct
{
? ? int x1 ,y1 ,x2 ,y2;
}HDP;


typedef struct
{
? ? int x ,y;
}NODE;


typedef struct
{
? ? char c;
? ? int id;
}ANS;


STAR E1[N_edge] ,E2[N_edge];
HDP hdp[N_node];
NODE node[N_node];
ANS ans[N_node];
int list1[N_node] ,list2[N_node] ,tot;
int dep1[N_node] ,mkuse1[N_node];
int dep2[N_node] ,mkuse2[N_node];


bool camp(ANS a ,ANS b)
{
? ? return a.c < b.c;
}


void add(int a ,int b)
{
? ? E1[++tot].to = b;
? ? E1[tot].next = list1[a];
? ? list1[a] = tot;


? ? E2[tot].to = a;
? ? E2[tot].next = list2[b];
? ? list2[b] = tot;
}


bool jude(HDP a ,NODE b)
{
? ? return a.x1 <= b.x && a.x2 >= b.x && a.y1 <= b.y && a.y2 >= b.y;
}


int main ()
{
? ? int n ,i ,j ,cas = 1;
? ? while(~scanf("%d" ,&n) && n)
? ? {
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%d %d %d %d" ,&hdp[i].x1 ,&hdp[i].x2 ,&hdp[i].y1 ,&hdp[i].y2);
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%d %d" ,&node[i].x ,&node[i].y);
? ? ? ? memset(list1 ,0 ,sizeof(list1));
? ? ? ? memset(list2 ,0 ,sizeof(list2));
? ? ? ? tot = 1;
? ? ? ? memset(dep1 ,0 ,sizeof(dep1));
? ? ? ? memset(dep2 ,0 ,sizeof(dep2));
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? ? if(jude(hdp[i] ,node[j]))
? ? ? ? {
? ? ? ? ? ? add(i ,j);
? ? ? ? ? ? dep1[i] ++;
? ? ? ? ? ? dep2[j] ++;
? ? ? ? }
? ? ? ? int ansid = 0;
? ? ? ? memset(mkuse1 ,0 ,sizeof(mkuse1));
? ? ? ? memset(mkuse2 ,0 ,sizeof(mkuse2));
? ? ? ? while(1)
? ? ? ? {
? ? ? ? ? ? int mk = 0;
? ? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(dep1[i] == 1 && !mkuse1[i])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mkuse1[i] = 1;
? ? ? ? ? ? ? ? ? ? mk = 1;
? ? ? ? ? ? ? ? ? ? int to;
? ? ? ? ? ? ? ? ? ? for(int k = list1[i] ;k ;k = E1[k].next)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? if(!mkuse2[E1[k].to])
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? mkuse2[E1[k].to] = 1;
? ? ? ? ? ? ? ? ? ? ? ? ? ? to = E1[k].to;
? ? ? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? dep2[to] --;
? ? ? ? ? ? ? ? ? ? for(int k = list2[to] ;k ;k = E2[k].next)
? ? ? ? ? ? ? ? ? ? dep1[E2[k].to] --;
? ? ? ? ? ? ? ? ? ? ans[++ansid].c = i + 'A' - 1;
? ? ? ? ? ? ? ? ? ? ans[ansid].id = to;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }


? ? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(dep2[i] == 1 && !mkuse2[i])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mkuse2[i] = 1;
? ? ? ? ? ? ? ? ? ? mk = 1;
? ? ? ? ? ? ? ? ? ? int to;
? ? ? ? ? ? ? ? ? ? for(int k = list2[i] ;k ;k = E2[k].next)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? if(!mkuse1[E2[k].to])
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? mkuse1[E2[k].to] = 1;
? ? ? ? ? ? ? ? ? ? ? ? ? ? to = E2[k].to;
? ? ? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? dep1[to] --;
? ? ? ? ? ? ? ? ? ? for(int k = list1[to] ;k ;k = E1[k].next)
? ? ? ? ? ? ? ? ? ? dep2[E1[k].to] --;
? ? ? ? ? ? ? ? ? ? ans[++ansid].c = to + 'A' - 1;
? ? ? ? ? ? ? ? ? ? ans[ansid].id = i;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if(!mk) break;
? ? ? ? }
? ? ? ? printf("Heap %d\n" ,cas ++);
? ? ? ? if(!ansid) printf("none\n");
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? sort(ans + 1 ,ans + ansid + 1 ,camp);
? ? ? ? ? ? for(i = 1 ;i <= ansid ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(i == 1) printf("(%c,%d)" ,ans[i].c ,ans[i].id);
? ? ? ? ? ? ? ? else printf(" (%c,%d)" ,ans[i].c ,ans[i].id);
? ? ? ? ? ? }
? ? ? ? ? ? printf("\n");
? ? ? ? }
? ? ? ? printf("\n");


? ? }
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的POJ1486模拟或者匈牙利变种的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。