当前位置:网站首页>P3033 [usaco11nov]cow steelchase g (similar to minimum path coverage)

P3033 [usaco11nov]cow steelchase g (similar to minimum path coverage)

2022-07-06 04:03:00 Zhong Zhongzhong

https://www.luogu.com.cn/problem/P3033
P3033 [USACO11NOV]Cow Steeplechase G
Cried and cried , I originally wanted to watch online classes , This inscription cost me a lot 2 hours .... Fortunately, it's a blue question , Or you'll lose a lot
Seriously summarize :
1. First 250250 Data over 10000 , Be sure to use the chained forward star method to save the map .
2. The difficulty of this problem lies in the establishment of graphics , Take the vertical line segment as the upper node , The lower node intersecting with it establishes a line segment ; The horizontal line serves as the lower node , Find the maximum matching tree , This is the minimum vertex covering
3.n- This value , The rest of the line segments have nothing to do with each other , That's the answer. .
4. The rest is the template of Hungarian algorithm
*

#include <bits/stdc++.h>
#define y1 y11
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
int link[maxn],n,head[maxn],cnt;
int p[maxn],x1[maxn],y1[maxn],x2[maxn],y2[maxn],n1;
bool used[maxn];
struct node
{
    
    int to,nxt;
}e[maxn];
void add_edge(int from,int to)
{
    
    e[++cnt].to=to;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
bool dfs(int u)
{
    
    for(int i=head[u];i;i=e[i].nxt)
    {
    
        int v=e[i].to;
        if(!used[v])
        {
    
            used[v]=1;
            if(link[v]==-1||dfs(link[v]))
            {
    
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int hungary()
{
    
    memset(link,-1,sizeof(link));
    int ret=0;
    for(int i=1;i<=n;i++)
    {
    
        if(p[i]==2)
            continue;
        memset(used,0,sizeof(used));
        if(dfs(i))
            ret++;
    }
    return ret;
}
int main()
{
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    
        scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
        if(x1[i]>x2[i]) swap(x1[i],x2[i]);
        if(y1[i]>y2[i]) swap(y1[i],y2[i]);
        if(x1[i]==x2[i]) p[i]=1,n1++;  // Number of vertical points 
        else
            p[i]=2;
    }
    for(int i=1;i<=n;i++)
    {
    
        for(int j=i+1;j<=n;j++)
        {
    
            if(p[i]==1&&p[j]==2)
            {
    
                if(x1[i]>=x1[j]&&x2[i]<=x2[j]&&y1[i]<=y1[j]&&y2[i]>=y2[j])
                    add_edge(i,n1+j);
            }
            else if(p[i]==2&&p[j]==1)
            {
    
                if(x1[i]<=x1[j]&&x2[i]>=x2[j]&&y1[i]>=y1[j]&&y2[i]<=y2[j])
                    add_edge(j,n1+i);
            }
        }
    }
    printf("%d\n",n-hungary());
    return 0;
}
原网站

版权声明
本文为[Zhong Zhongzhong]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/02/202202132248191405.html

随机推荐