HDU 4619 Warm up 2（最大獨立集）

HDU 4619 Warm up 2

Problem Description

Some 1×2 dominoes are placed on a plane. Each dominoe is placed either horizontally or vertically. It’s guaranteed the dominoes in the same direction are not overlapped, but horizontal and vertical dominoes may overlap with each other. You task is to remove some dominoes, so that the remaining dominoes do not overlap with each other. Now, tell me the maximum number of dominoes left on the board.

Input

There are multiple input cases.The first line of each case are 2 2 2 integers: n ( 1 &lt; = n &lt; = 1000 ) , m ( 1 &lt; = m &lt; = 1000 ) n(1 &lt;= n &lt;= 1000), m(1 &lt;= m &lt;= 1000) n(1<=n<=1000),m(1<=m<=1000), indicating the number of horizontal and vertical dominoes.

Then n n n lines follow, each line contains 2 2 2 integers x ( 0 &lt; = x &lt; = 100 ) x (0 &lt;= x &lt;= 100) x(0<=x<=100) and y ( 0 &lt; = y &lt; = 100 ) y (0 &lt;= y &lt;= 100) y(0<=y<=100), indicating the position of a horizontal dominoe. The dominoe occupies the grids of ( x , y ) (x, y) (x,y) and ( x + 1 , y ) (x + 1, y) (x+1,y)

Then m m m lines follow, each line contains 2 2 2 integers x ( 0 &lt; = x &lt; = 100 ) x (0 &lt;= x &lt;= 100) x(0<=x<=100) and y ( 0 &lt; = y &lt; = 100 ) y (0 &lt;= y &lt;= 100) y(0<=y<=100), indicating the position of a horizontal dominoe. The dominoe occupies the grids of ( x , y ) (x, y) (x,y) and ( x , y + 1 ) (x, y + 1) (x,y+1).

Input ends with n = 0 n = 0 n=0 and m = 0 m = 0 m=0.

Output

For each test case, output the maximum number of remaining dominoes in a line.

Sample Input

2 3
0 0
0 3
0 1
1 1
1 3
4 5
0 1
0 2
3 1
2 2
0 0
1 0
2 0
4 1
3 2
0 0
           

Sample Output

4
6
           

∙ \bullet ∙題意：有 n n n條水準和 m m m條豎直的機關長度的線段，規定同為水準或者豎直的線段怎麼放都不算重疊，隻有水準和豎直的線段有交點的時候算重疊。輸入 n n n個點 ( x , y ) (x,y) (x,y)那麼這條水準線段的令一個端點就是 ( x + 1 , y ) (x+1,y) (x+1,y)，再輸入 m m m個坐标代表豎直線段。問從坐标系中找出最多多少條的線段，這些線段不能重疊。

∙ \bullet ∙思路：剛學二分最大比對可能想不到怎麼做這個題，建議先去了解一下最大獨立集，最大獨立集=頂點數-最大比對邊數。什麼是最大獨立集：在二分圖中選出最多的點，使得任意兩兩點之間都沒有邊，就是任意兩兩點之間都關系。既然這個題裡要求最多的線段不重疊，那麼就可以在有重疊的線段之間建邊，然後再求最大獨立集就行了。這個題建邊是個麻煩事。

∙ \bullet ∙題意我們可以用一個二維數組 v i s [ i ] [ j ] vis[i][j] vis[i][j]代表 ( i , j ) (i,j) (i,j)這個坐标已經被哪個頂點占用了（把線段抽象為頂點，頂點的編号就按照輸入順序編就行了），如果在某次輸入頂點的坐标 ( x , y ) (x,y) (x,y)或者 ( x + 1 , y ) (x+1,y) (x+1,y)或者 ( x , y + 1 ) (x,y+1) (x,y+1)已經被前面的某個頂點占用了，那就在這兩個頂點間建一條無向邊，再把 v i s [ x ] [ y ] vis[x][y] vis[x][y]或 v i s [ x + 1 ] [ y ] vis[x+1][y] vis[x+1][y]或 v i s [ x ] [ y + 1 ] vis[x][y+1] vis[x][y+1]更新成目前的頂點的編号。這樣就能在輸入的時候就把邊建好了。最後在跑一次匈牙利算法就行了，注意最後得到的最大比對邊數要➗2。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<iostream>
#include<queue>
#include<string>
#include<math.h>
typedef long long LL;
using namespace std;
const int maxn=1e4+10;
int n,m;
int vis[150][150],used[2500],match[2500];

struct node{int to,next;}e[maxn];///鍊式前向星存邊
int cnt = 0,head[maxn];
void add(int s,int E)
{
    e[++cnt] = {E,head[s]};
    head[s] = cnt;
}

bool dfs(int x)///匈牙利算法
{
    if(used[x])return false;
    for(int i = head[x];i != -1;i = e[i].next){
        int to = e[i].to;
        if(!used[to]){
            used[to] = 1;
            if(match[to] == -1||dfs(match[to])){
                match[to] = x;
                return true;
            }
        }
    }
    return false;
}

void input()
{
    for(int i = 1;i <= n;i++){///輸入n條水準的線段
        int x,y;
        scanf("%d%d",&x,&y);
        if(vis[x][y] != -1 && vis[x][y] != i){///注意不能和自己建邊
            add(i,vis[x][y]);
            add(vis[x][y],i);
        }
        if(vis[x+1][y] != -1 && vis[x+1][y] != i){
            add(i,vis[x+1][y]);
            add(vis[x+1][y],i);
        }
        vis[x][y] = i;vis[x+1][y] = i;
    }
    for(int i = n+1;i <= m+n;i++){///輸入m條豎直的線段
        int x,y;
        scanf("%d%d",&x,&y);
        if(vis[x][y] != -1 && vis[x][y] != i){
            add(i,vis[x][y]);
            add(vis[x][y],i);
        }
        if(vis[x][y+1] != -1 && vis[x][y+1] != i){
            add(i,vis[x][y+1]);
            add(vis[x][y+1],i);
        }
        vis[x][y] = i;vis[x][y+1] = i;
    }
}

void init()
{
    cnt = 0;
    memset(head,-1,sizeof(head));
    memset(e,0,sizeof(e));
    memset(vis,-1,sizeof(vis));///初始化為-1
    memset(match,-1,sizeof(match));
}

int main()
{
    while(scanf("%d%d",&n,&m) && n + m)
    {
        init();
        input();
        int ans = 0;
        for(int i = 1;i <= n + m;i++){
            memset(used,0,sizeof(used));
            if( dfs(i) )
                ans ++;
        }
        printf("%d\n",n + m - ( ans / 2 ));
    }
    return 0;
}