给出 N 条平行于坐标轴的线段,要你选出尽量多的线段使得这些线段两两没有交点(顶点也算)。
横的与横的,竖的与竖的线段之间保证没有交点,输出最多能选出多少条线段。
#include <iostream> #include <algorithm> #include <cstring> #include <queue> using namespace std ; const int N =1e4, M=3e6+2; const int inf =1e9; int b[N],x1[N],x2[N],y1[N],y2[N]; int all=1,hd[N],go[M],w[M],nxt[M]; int S,T,n,m; int dis[M],ans=0,now[M]; void add_(int x,int y,int z){ nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=z; swap(x,y); nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=0; } bool bfs(){ for(int i=0;i<M;i++)dis[i]=inf; queue<int> q; q.push(S); now[S]=hd[S]; dis[S]=0; while(q.empty()==0){ int x=q.front(); q.pop(); for(int i=hd[x];i;i=nxt[i]){ int y=go[i]; if(w[i]>0&&dis[y]==inf){ dis[y]=dis[x]+1; now[y]=hd[y]; q.push(y); if(y==T) return 1; } } } return 0; } int dfs(int x,int sum){ if(x==T) return sum; int k,res=0; for(int i=now[x];i&& sum ;i=nxt[i]){ now[x]=i; int y=go[i]; if(w[i]>0&&(dis[y]==dis[x]+1)){ k=dfs(y,min(sum,w[i])); if(k==0) dis[y]=inf; w[i]-=k; w[i^1]+=k; res+=k; sum-=k; } } return res; } void dinic(){ int ans=0; while(bfs()) ans+=dfs(S,inf); cout<<n-ans<<endl; } signed main(){ cin>>n; S=0,T=n+1; int i,j; for(i=1;i<=n;i++){ cin>>x1[i]>>y1[i]>>x2[i]>>y2[i]; if(x1[i]==x2[i]) b[i]=1; else b[i]=2; } for(i=1;i<=n;i++) if(b[i]==1) add_(S,i,1); for(i=1;i<=n;i++) if(b[i]==2) add_(i,T,1); for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(i!=j&&b[i]==1&&b[j]==2){ int Y1=y1[i],Y2=y2[i],Y3=y1[j]; if(Y1<Y2) swap(Y1,Y2); int X1=x1[j],X2=x2[j],X3=x1[i]; if(X1>X2) swap(X1,X2); if(Y1>=Y3&&Y2<=Y3&&X1<=X3&&X2>=X3) add_(i,j,1); } } dinic(); }