「USACO11NOV」牛的障碍Cow Steeplechase 解题报告

题面

横的，竖的线短段，求最多能取几条没有相交的线段？

思路

学过网络流的童鞋在哪里？

是时候重整网络流雄风了！

好吧，废话不多说

这是一道最小割的题目

怎么想呢？

要取最多，那反过来不就是不能取的要尽量少吗？

深思熟虑一番后，符合网络流中的最小割，于是开码

哦，还没完！

建边是关键！

由于只有方向不同的线段才会互相影响，所以考虑在方向不同时建边

由于最小割的用途是使图不连通，所以我们把横的线段与源点相连，竖的线段与汇点相连（相反也可以），在有相交的线段之间建一条边，表示能连通，这样就变成了求最小割

但是！

要注意的是：由于题目的要求是取线段，而不是我们建的边，因此我们把一个点（线段）拆成入点和出点，在入点和出点之间建一条容量为1的边，其余边的容量都赋为INF，这样就肯定不会“割”去边，只会“割”去点

还有！

怎么判断线段香蕉相交呢？

画出来就知道了

这个小问题，就留给大家思考吧

Code：

#include<bits/stdc++.h>//虽然我不想写注释

#define INF 0x7f7f7f7f//但是不写注释的不是好孩纸？！h^ovny：谁说的！

#define M 65010

#define N 510

using namespace std;

struct Node{

	int lx,ly,rx,ry,i;

	Node(int a,int b,int c,int d,int e):lx(a),ly(b),rx(c),ry(d),i(e){	}

	Node(){	}

}A[N>>1],B[N>>1];//这个是分开存横的和竖的线段

struct node{

	int to,cap;

	int nxt;

	node(int a,int b):to(a),cap(b){	}

	node(){	}

}b[M<<1];//边

int head[N],deep[N];

int n,Maxflow,S,T,t=1,ta,tb;

int read()

{

	int s=0;

	char c=getchar();

	while(!isdigit(c))

		c=getchar();

	while(isdigit(c))

	{

		s=(s<<1)+(s<<3)+c-'0';

		c=getchar();

	}

	return s;

}

void add(int x,int y,int cap)//建边，比较冗长，别介意

{

	b[++t]=node(y,cap);

	b[t].nxt=head[x];

	head[x]=t;

	b[++t]=node(x,0);

	b[t].nxt=head[y];

	head[y]=t;

	return;

}

bool BFS()

{

	int i,cur;

	int to,cap;

	queue<int>p;

	memset(deep,0,sizeof(deep));

	deep[S]=1;p.push(S);

	while(!p.empty())

	{

		cur=p.front();p.pop();

		for(i=head[cur];i;i=b[i].nxt)

		{

			to=b[i].to;cap=b[i].cap;

			if(cap&&!deep[to])

			{

				deep[to]=deep[cur]+1;

				p.push(to);

				if(to==T)

					return 1;

			}

		}

	}

	return 0;

}

int Dinic(int k,int flow)

{

	if(k==T)

		return flow;

	int i,to,cap,res,rest=flow;

	for(i=head[k];i&&rest;i=b[i].nxt)

	{

		to=b[i].to;cap=b[i].cap;

		if(cap&&deep[to]==deep[k]+1)

		{

			res=Dinic(to,min(rest,cap));

			if(!res)

				deep[to]=0;

			b[i].cap-=res;

			b[i^1].cap+=res;

			rest-=res;

		}

	}

	return flow-rest;

}

int main()

{

	int i,j,flow;

	int lx,ly,rx,ry;

	n=read();T=n+n+1;//源点一般赋为0，那就先确定汇点

	for(i=1;i<=n;i++)//读入，然后开始玄学建边

	{

		lx=read();ly=read();

		rx=read();ry=read();

		if(lx==rx)

		{

			B[++tb]=Node(min(lx,rx),min(ly,ry),max(lx,rx),max(ly,ry),i);//注意，要是两端点有序！

			add(S,i,INF);

			for(j=1;j<=ta;j++)//判断是否满足，然后建边

				if(B[tb].ry>=A[j].ly&&B[tb].ly<=A[j].ly&&A[j].lx<=B[tb].lx&&B[tb].lx<=A[j].rx)

					add(i+n,A[j].i,INF);

		}

		else

		{

			A[++ta]=Node(min(lx,rx),min(ly,ry),max(lx,rx),max(ly,ry),i);

			add(i+n,T,INF);//一切同上

			for(j=1;j<=tb;j++)

				if(B[j].ry>=A[ta].ly&&B[j].ly<=A[ta].ly&&A[ta].lx<=B[j].lx&&B[j].lx<=A[ta].rx)

					add(B[j].i+n,i,INF);

		}

		add(i,i+n,1);//自己的入点和出点之间建边

	}

	while(BFS())//Dinic模板直接搬

		while((flow=Dinic(S,INF)))

			Maxflow+=flow;

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

	return 0;

}

巴特西

「USACO11NOV」牛的障碍Cow Steeplechase 解题报告

题面

思路

这是一道最小割的题目

建边是关键！

还有！

最新文章

热门文章