[HOJ 155][USACO 2011 Gold] 線段相交

作法：

把線段們都看成點，並且如果兩條線段不能同時取就在那兩個點之間連邊，那麼就會得到一張二部圖( 直的和橫的 )，問題就變成要求這個二部圖的最大獨立集大小。而對於一個圖的獨立集，考慮他的補集，這個集合就會滿足「對於圖中的所有邊，他的兩端點裡至少有一個點會落在這個集合中」，也就是一個 vertex cover 。而有個有名的定理告訴我們二部圖的最小點覆蓋數會等於最大匹配數，所以就直接求最大匹配數即可。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=250+5 ;
 
struct seg{int x1,y1,x2,y2;}a[maxn],b[maxn];
bool inter(const seg &p,const seg &q)
{
    return p.y1<=q.y1 && p.y2>=q.y1 && q.x1<=p.x1 && q.x2>=p.x2 ;
}
 
bool adj[maxn][maxn] ;
bool visy[maxn] ;
int n,m,my[maxn] ;
 
bool dfs(int x)
{
    for(int i=0;i<m;i++) if(adj[x][i] && !visy[i])
    {
        visy[i]=1 ;
        if(my[i]==-1 || dfs(my[i]))
        {
            my[i]=x ;
            return 1 ;
        }
    }
    return 0 ;
}
 
main()
{
    int k ; scanf("%d",&k) ;
    while(k--)
    {
        seg s ;
        scanf("%d%d%d%d",&s.x1,&s.y1,&s.x2,&s.y2) ;
        if(s.x1>s.x2) swap(s.x1,s.x2) ;
        if(s.y1>s.y2) swap(s.y1,s.y2) ;
        if(s.x1 == s.x2) a[n++]=s ;
        else b[m++]=s ;
    }
 
    if(!n || !m) { printf("%d\n", n ? n : m) ; return 0 ; }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        adj[i][j]=inter(a[i],b[j]) ;
 
    memset(my,-1,sizeof(my)) ;
    int ans=0 ;
    for(int i=0;i<n;i++)
    {
        memset(visy,0,sizeof(visy)) ;
        if(dfs(i)) ans++ ;
    }
    printf("%d\n",m+n-ans) ;
}