USACO11NOV Cow Steeplechase

发表于 | 分类于 |
字数统计: 426 字

题目地址

题解

把线段抽象成点，线段相交就连一条边，然后求一个最大独立集。
由于在二分图中，最大匹配就等于最小顶点覆盖，并且对于图来说，最大独立集加上最小顶点覆盖就等于点个数，所以直接上二分图匹配就行了。
线段求交…计算几何

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int n,vis[255],match[255]={0},seg[255][4];
int X[255],Y[255],cx=0,cy=0;
bool mat[255][255]={0};
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}	
int Edmond(int S){
    for(int i=1;i<=cy;i++){
        if(mat[S][i]&&!vis[i]){
            vis[i]=1;
            if(!match[i]||Edmond(match[i])){
                match[i]=S;
                return 1;
            }
        }
    }
    return 0;
}
void init(){
    n=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=4;j++)
            seg[i][j]=read();
        if(seg[i][1]==seg[i][3]){
            Y[++cy]=i;//竖直 
            if(seg[i][2]>seg[i][4])
                swap(seg[i][2],seg[i][4]);
        }else {
            X[++cx]=i;//水平
            if(seg[i][1]>seg[i][3])
                swap(seg[i][1],seg[i][3]);
        } 
    }
    for(int i=1;i<=cx;i++)
        for(int j=1;j<=cy;j++)
            if(seg[Y[j]][1]>=seg[X[i]][1]&&seg[Y[j]][1]<=seg[X[i]][3]&&
                seg[X[i]][2]>=seg[Y[j]][2]&&seg[X[i]][2]<=seg[Y[j]][4])
                mat[i][j]=1;
}
void solve(){
    int ans=0;
    for(int i=1;i<=cx;i++){
        memset(vis,0,sizeof(vis));
        if(Edmond(i))ans++;
    }
    printf("%d\n",n-ans);
}
int main(){
    init();
    solve();
    return 0;
}

Powered By Valine
v1.5.2