镜面通道 bzoj-3630 JLOI-2014

题目大意题目链接

注释:略。


想法

我们发现,只要上下界没有被完全封死,我们就一定有一条合法的光路。

所以只需要将上界和下界拆开即可。

拆点,把每个点分为入点和出点,入点向出点连1的边。

元件之间如果连通就连$inf$。

和上界连通就对源点连$inf$,和下界连通就和汇点连$inf$。

最后求最小割即为答案。

Code

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 303
#define M 370000
#define inf 0x7fffffff
#define ll long long
using namespace std;
int to[M],hd[M],lk[N<<1],len[M],cnt=1,T;
void add(int u,int v,int w)
{
to[++cnt]=v,hd[cnt]=lk[u],len[cnt]=w,lk[u]=cnt;
to[++cnt]=u,hd[cnt]=lk[v],lk[v]=cnt;
}
struct pt
{
ll x,y;
void read()
{scanf("%lld%lld",&x,&y);}
}tp1,tp2;
inline ll Dis(pt a,pt b)
{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
struct cir
{pt o;int r;}Cir[N];
struct rec
{pt x1,x2;}Rec[N],ss,tt;
short n,loc[N];
int X,Y,ans;
ll d,xx,yy;
bool judge(cir a,rec b)
{
d=a.r,xx=a.o.x,yy=a.o.y;
if(xx>=b.x1.x-d&&xx<=b.x2.x+d&&yy>=b.x1.y&&yy<=b.x2.y
||xx>=b.x1.x&&xx<=b.x2.x&&yy>=b.x1.y-d&&yy<=b.x2.y+d)return 1;
tp1.x=b.x1.x,tp2.y=b.x2.y,tp2.x=b.x2.x,tp2.y=b.x1.y;d*=d;
return Dis(a.o,tp1)<=d||Dis(a.o,tp2)<=d||Dis(a.o,b.x1)<=d||Dis(a.o,b.x2)<=d;
}
bool check(int a,int b)
{
if(loc[a]>loc[b])swap(a,b);
if(loc[b]<2)return((Cir[a].r+Cir[b].r)*(Cir[a].r+Cir[b].r)>=Dis(Cir[a].o,Cir[b].o));
if(loc[a]>1)return (Rec[a].x1.x<=Rec[b].x1.x&&Rec[b].x1.x<=Rec[a].x2.x||
Rec[a].x1.x<=Rec[b].x2.x&&Rec[b].x2.x<=Rec[a].x2.x)&&
(Rec[a].x1.y<=Rec[b].x1.y&&Rec[b].x1.y<=Rec[a].x2.y||
Rec[a].x1.y<=Rec[b].x2.y&&Rec[b].x2.y<=Rec[a].x2.y);
return judge(Cir[a],Rec[b]);
}
int k,q[N<<1],h,t,dis[N<<1],cur[N<<1];
bool bfs()
{
for(int i=0;i<=T;i++)
dis[i]=0,cur[i]=lk[i];
h=0,t=dis[0]=1;
while(h<t)
{
k=q[h++];
for(int i=lk[k];i;i=hd[i])
if(len[i]&&!dis[to[i]])
dis[q[t++]=to[i]]=dis[k]+1;
}
return dis[T];
}
int dfs(int x,int f)
{
if(x==T||!f)return f;
int r=0,cst;
for(int &i=cur[x];i;i=hd[i])
if(dis[to[i]]==dis[x]+1)
{
cst=dfs(to[i],f<len[i]?f:len[i]);
f-=cst,len[i]-=cst;
r+=cst,len[i^1]+=cst;
if(!f)break;
}
if(!r)dis[x]=0;
return r;
}
int main()
{
scanf("%d%d",&X,&Y);
ss={{0,0},{X,0}};tt={{0,Y},{X,Y}};
scanf("%d",&n);T=n<<1|1;
for(int i=1;i<=n;i++)
{
add(i,i+n,1);
scanf("%d",loc+i);
if(loc[i]<2)
{
Cir[i].o.read(),scanf("%lld",&Cir[i].r);
if(judge(Cir[i],ss))add(0,i,inf);
if(judge(Cir[i],tt))add(i+n,T,inf);
}
else
{
Rec[i].x1.read(),Rec[i].x2.read();
if(Rec[i].x1.y<=0&&Rec[i].x1.x<=X&&Rec[i].x2.x>=0)add(0,i,inf);
if(Rec[i].x2.y>=Y&&Rec[i].x1.x<=X&&Rec[i].x2.x>=0)add(i+n,T,inf);
}
for(int j=1;j<i;j++)
if(check(j,i))
add(j+n,i,inf),add(i+n,j,inf);
}
while(bfs())ans+=dfs(0,inf);
printf("%d",ans);
}

小结:好题好题。就是特判有点恶心。

最新文章

  1. Android开发1:基本UI界面设计——布局和组件
  2. C# static成员的构造顺序
  3. iOS中控制器的释放问题
  4. POJ3083 Children of the Candy Corn(Bfs + Dfs)
  5. JavaScript设计模式(3)-工厂模式
  6. http状态码是什么,有什么用,在哪里查看,分别代表什么意思?
  7. oracle11g导出表时会发现少表,空表导不出解决方案。
  8. ROS_Kinetic_20 ROS基础补充
  9. 这些好用的 Chrome 插件,提升你的工作效率
  10. @PostConstruct 和 @PreConstruct
  11. PHP连接mysql数据库报错:Call to undefined function mysql_connect()
  12. vue-cli+webpack+router+vuex---之vuex使用
  13. Django--视图函数views
  14. Android学习之基础知识十二 — 第一讲:网络技术的使用
  15. ALGO-152_蓝桥杯_算法训练_8-2求完数
  16. Java 8- Java 分支结构 - if…else/switch
  17. [转]vue全面介绍--全家桶、项目实例
  18. 609E- Minimum spanning tree for each edge
  19. Java编程的逻辑 (66) - 理解synchronized
  20. Zabbix3.4-部署安装

热门文章

  1. AJPFX关于多态中的动态绑定和静态绑定的总结
  2. SpringSecurity的简单使用
  3. react学习文档
  4. 学习 微信小程序 大神不要笑
  5. OpenGL VAO, VBO 使用简介
  6. 开源一个一个NodeJS 代理服务器扫描工具,可以用来***
  7. leetcode_357. Count Numbers with Unique Digits
  8. Mysql基本操作、C++Mysql简单应用、PythonMysql简单应用
  9. CAD参数绘制圆(com接口)
  10. 【计算机网络】2.6 P2P应用