题意

题目描述

   --+-------

-----+-----

  ---+---     |

     |     |  |

   --+-----+--+-   |

     |     |  |  | |

     |   --+--+--+-+-

           |  |  | |

              |

   ----------

-----------

  -------     |

           |  |

           |  |    |

           |  |  | |

           |  |  | |

           |  |  | |

              |

给出\(N\)平行于坐标轴的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算），横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段。

输入输出样例

输入样例#1：

输出样例#1：

思路

其实这题就一句话：二分图最大独立集大小=总点数-最大匹配数。

二分图匹配就好了。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=255;

int n,ans,match[MAXN],xx[MAXN],yy[MAXN],xxx[MAXN],yyy[MAXN];

int cnt,top[MAXN],to[MAXN*MAXN],nex[MAXN*MAXN];

bool vis[MAXN];

int read()

{

    int re=0;char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();

    return re;

}

void add_edge(int x,int y){to[++cnt]=y,nex[cnt]=top[x],top[x]=cnt;}

bool dfs(int now)

{

    for(int i=top[now];i;i=nex[i])

        if(!vis[to[i]])

        {

            vis[to[i]]=true;

            if(!match[to[i]]||dfs(match[to[i]]))

            {

                match[to[i]]=now;

                return true;

            }

        }

    return false;

}

int main()

{

    n=read();

    for(int i=1;i<=n;i++)

    {

        xx[i]=read(),yy[i]=read(),xxx[i]=read(),yyy[i]=read();

        if(xx[i]>xxx[i]) swap(xx[i],xxx[i]);

        if(yy[i]>yyy[i]) swap(yy[i],yyy[i]);

    }

    for(int i=1;i<=n;i++)

    {

        if(xx[i]!=xxx[i]) continue;

        for(int j=1;j<=n;j++)

        {

            if(yy[j]!=yyy[j]) continue;

            if(yy[i]<=yy[j]&&yy[j]<=yyy[i]&&xx[j]<=xx[i]&&xx[i]<=xxx[j]) add_edge(i,j);

        }

    }

    for(int i=1;i<=n;i++)

        if(xx[i]==xxx[i])

        {

            memset(vis,false,sizeof vis);

            if(dfs(i)) ans++;

        }

    printf("%d",n-ans);

    return 0;

}

巴特西

Luogu P3033 [USACO11NOV]牛的障碍Cow Steeplechase(二分图匹配)

题意

题目描述

输入输出样例

输入样例#1：

输出样例#1：

思路

AC代码

最新文章

热门文章