https://www.luogu.org/fe/problem/P3033
二分图最大独立集
注意输入的时候控制x1,y1,x2,y2的相对大小.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
/* dinic begin */
const int MAXN=5000;
const int MAXM=120000;
//注意网络流要预留反向边
const int INF=0x3f3f3f3f;
struct Edge{
int to,next,cap,flow;
}edge[MAXM];
int tol;
int head[MAXN];
void init(){
tol=2;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w=1,int rw=0){
edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;
edge[tol].next=head[u];head[u]=tol++;
edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0;
edge[tol].next=head[v];head[v]=tol++;
}
int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n){
int front=0,tail=0;
memset(dep,-1,sizeof(dep[0])*(n+1));
dep[s]=0;
Q[tail++]=s;
while(front<tail){
int u=Q[front++];
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(edge[i].cap>edge[i].flow&&dep[v]==-1){
dep[v]=dep[u]+1;
if(v==t)
return true;
Q[tail++]=v;
}
}
}
return false;
}
int dinic(int s,int t,int n=-1){
int maxflow=0;
if(n==-1)
n=t;
n++;//假如把t作为编号最后的点的话传入t就可以了
while(bfs(s,t,n)){
for(int i=0;i<n;i++)cur[i]=head[i];
int u=s,tail=0;
while(cur[s]!=-1){
if(u==t){
int tp=INF;
for(int i=tail-1;i>=0;i--){
tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
}
maxflow+=tp;
for(int i=tail-1;i>=0;i--){
edge[sta[i]].flow+=tp;
edge[sta[i]^1].flow-=tp;
if(edge[sta[i]].cap-edge[sta[i]].flow==0)
tail=i;
}
u=edge[sta[tail]^1].to;
}
else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow
&&dep[u]+1==dep[edge[cur[u]].to]){
sta[tail++]=cur[u];
u=edge[cur[u]].to;
}
else{
while(u!=s&&cur[u]==-1){
u=edge[sta[--tail]^1].to;
}
cur[u]=edge[cur[u]].next;
}
}
}
return maxflow;
}
/* 备注：
1.检查MAXN与MAXM，注意预留反向边和额外边的位置
2.每次建图的第一次addedge()前必须先init()
3.不传入第三参数的dinic(s,t)需保证t是最后的结点
*/
/* dinic end */
struct Line{
int x1,y1,x2,y2;
Line(){}
inline void input(){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>x2)
swap(x1,x2);
if(y1>y2)
swap(y1,y2);
}
inline bool intersection(Line &l){
if(x1==x2){
if(l.x1==l.x2)
return false;
else{
if(l.x1<=x1&&x1<=l.x2&&y1<=l.y1&&l.y1<=y2)
return true;
else
return false;
}
}
else{
if(l.y1==l.y2)
return false;
else{
if(l.y1<=y1&&y1<=l.y2&&x1<=l.x1&&l.x1<=x2)
return true;
else
return false;
}
}
}
inline bool samex(){
return x1==x2;
}
}line[5000];
int main(){
init();
int n;
scanf("%d",&n);
int s=0,t=n+1;
for(int i=1;i<=n;i++){
line[i].input();
if(line[i].samex()){
addedge(s,i);
}
else{
addedge(i,t);
}
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(line[i].intersection(line[j])){
if(line[i].samex())
addedge(i,j);
else
addedge(j,i);
}
}
}
int ans=n-dinic(s,t);
printf("%d\n",ans);
}