注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2965]保护古迹  

2015-06-20 15:42:24|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2965: 保护古迹

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 277  Solved: 101
[Submit][Status][Discuss]

Description

  某校由于历史悠久,校园中有大量的名胜古迹。为了更好地保护这些古迹,学校决定用篱笆将这些古迹围起来。
  现在已知有p个地点的古迹需要保护。这些古迹可以看做二维平面上的整数点。有n个点可以作为篱笆的端点,这些端点的坐标也为二维平面上的整数。端点用1到n的整数编号。
  有m对端点之间可以修建篱笆。用(u,v,w)描述一段可以修建的篱笆,表示端点u和端点v之间可以花费w的代价修建一段。篱笆都看做直线段。为了方便设计,这些可以修建的篱笆都是不会相交的(只会在端点处相交)。
  将一个古迹围起来是指存在一个由篱笆构成的简单多边形,这个古迹在该多边形内部。
  由于经费问题,学校希望修建篱笆的花费最小。你需要输出将至少1个,2个,…,p个古迹围起来的最小花费。

Input

  第一行包含三个正整数p,n,m表示古迹的个数,端点个数和可以修建的篱笆条数。
  接下来p行,每行包含两个整数,表示每个古迹的坐标。
  接下来n行,每行包含两个整数,表示每个端点的坐标。这些端点按照输入的顺序依次用1到n的整数编号。
  最后m行,每行包含三个非负整数u,v,w,表示可以在端点u和端点v之间花w的代价修建一段篱笆。

Output

  输出p行,分别表示将至少1个,2个,…,p个古迹围起来的最小花费。

Sample Input

3 9 15 -2 2 2 1 2 -1 3 0 3 2 1 2 -1 3 -3 3 -2 1 1 0 2 -2 2 -3 1 2 20 1 7 40 1 8 10 1 9 100 2 3 50 3 4 1000 3 7 10 4 5 10 4 6 10 4 7 1000 5 6 10 6 7 1000 7 8 120 7 9 10 8 9 10

Sample Output

30 100 140

HINT


 对于100%的数据,n≤100, m≤C(n,2),p≤10。所有坐标位置的两维绝对值不超过109,u,v不超过n,w不超过106
  保证可以修建的篱笆不会经过古迹。保证可以修建的两段篱笆不会在非端点处相交或重合。保证至少存在一种方案可以包围所有古迹。保证n个点互不相同。

Source

Solution

为了复习平面图而写了这题。
前面就是平面图转对偶图+点定位
后面的话,由于只有10个点,2^10枚举哪个点被选,s向它们连边,t为无穷大的那片区域,求最小割即可。
开始还以为直接流就好了不用状压,然而似乎反例很好举?

Code

/**************************************************************
    Problem: 2965
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:196 ms
    Memory:916 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<set>
#include<algorithm>
#include<cstring>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int aa,bb;int F(){
    while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
}
typedef long long ll;
typedef double ld;
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define N 200
#define M 600
int n,m,t,id[N],tot,vis[M],la[N],et=1,inf,col,ans[20];ll sum[N];
struct E{int to,v,nxt,pre;}e[M];
struct P{
    int x,y;
    bool operator<(const P&a)const {return x<a.x||x==a.x&&y<a.y;}
    bool operator==(const P&a)const {return x==a.x&&y==a.y;}
    P operator-(const P&a)const {return (P){x-a.x,y-a.y};}
    ll operator*(const P&a)const {return 1LL*x*a.y-1LL*y*a.x;}
}p[N];
struct D{
    P p;int n;
    bool operator<(const D&a)const {return atan2(p.y,p.x)<atan2(a.p.y,a.p.x);}
}d[N],a[N];
bool cmp(const D&a,const D&b){return a.p<b.p||a.p==b.p&&a.n<b.n;}
void sort_edge(int x){
    int cnt=0;
    for(int i=la[x];i;i=e[i].nxt)d[++cnt]=(D){p[e[i].to]-p[x],i};
    std::sort(d+1,d+1+cnt);
    for(int i=2;i<=cnt;i++)e[d[i].n].pre=d[i-1].n;
    e[d[1].n].pre=d[cnt].n;
}
void get_area(int col,int i){
    int o=i,x=e[i^1].to;
    for(vis[i]=col;(i=e[i^1].pre)!=o;vis[i]=col)
    sum[col]+=(p[e[i].to]-p[x])*(p[e[i^1].to]-p[x]);
    if(sum[col]<0)sum[col]=-sum[col];
}
ld nowx;
struct T{
    struct Node{
        ld k,b,x0;int col;
        bool operator<(const Node&a)const {
            return k*(nowx+0.001)+b<a.k*(nowx+0.001)+a.b||
            k*(nowx+0.001)+b==a.k*(nowx+0.001)+a.b&&x0<a.x0;
        }
    }tr[M];
    std::set<Node>s;int tot;
    std::set<Node>::iterator it[M];
    void init(){
        for(int i=2;i<=et;i+=2){
            tr[i>>1].k=1.0*(p[e[i].to].y-p[e[i^1].to].y)/(p[e[i].to].x-p[e[i^1].to].x);
            tr[i>>1].b=p[e[i].to].y-tr[i>>1].k*p[e[i].to].x;
            tr[i>>1].x0=min(p[e[i].to].x,p[e[i^1].to].x);
            tr[i>>1].col=vis[i^(p[e[i].to].x<p[e[i^1].to].x)];
        }
        tr[0].b=-1,tr[0].col=inf;s.insert(tr[0]);tot=(et>>1)+1;
    }
    void ins(int x,int o){nowx=x,it[o]=s.insert(tr[o]).first;}
    void del(int o){s.erase(it[o]);}
    void query(int o,int x,int y){nowx=x,tr[tot].b=y,id[o-n]=(*--s.lower_bound(tr[tot])).col;}
}tree;
struct NF{
    int et,la[N],to[M],nxt[M],FL[M],fl[M],cur[N],d[N],q[N],l,r,tot,ola[N],s,t;
    void add(int x,int y,int v){
        to[++et]=y,FL[et]=v,nxt[et]=ola[x],ola[x]=et;
        to[++et]=x,FL[et]=v,nxt[et]=ola[y],ola[y]=et;
    }
    void adde(int x,int y,int v){
        to[++tot]=y,fl[tot]=v,nxt[tot]=la[x],la[x]=tot;
        to[++tot]=x,fl[tot]=0,nxt[tot]=la[y],la[y]=tot;
    }
    int bfs(){
        memset(d,0,sizeof(d));
        for(q[l=r=0]=t,d[t]=1;l<=r;l++)
        for(int i=la[q[l]];i;i=nxt[i])
        if(!d[to[i]]&&fl[i^1])d[q[++r]=to[i]]=d[q[l]]+1;
        return d[s];
    }
    int dfs(int x,int ret){
        if(x==t||ret==0)return ret;
        int tmp,flow=0;
        for(int&i=cur[x];i;i=nxt[i])
        if(d[to[i]]+1==d[x]){
            tmp=dfs(to[i],min(fl[i],ret-flow));
            fl[i]-=tmp,fl[i^1]+=tmp,flow+=tmp;
            if(flow==ret)return flow;
        }
        return flow;
    }
    int dinic(){
        int flow=0;
        while(bfs())memcpy(cur,la,sizeof(la)),flow+=dfs(s,1<<30);
        return flow;
    }
    int maxflow(int m){
        memset(ans,63,sizeof(ans));
        for(int S=1,cnt,i,x,tmp;S<1<<m;S++){
            memcpy(la,ola,sizeof(ola)),memcpy(fl,FL,sizeof(FL));
            for(tot=et,cnt=0,x=S,i=1;i<=m;i++,x>>=1)if(x&1)cnt++,adde(s,id[i],1<<30);
            for(tmp=dinic();cnt;cnt--)if(ans[cnt]>tmp)ans[cnt]=tmp;
        }
    }
}G;
int main(){
    t=F(),n=F(),m=F();tot=n;G.et=1;
    for(int i=1;i<=t;i++)a[++tot].p=(P){F(),F()},a[tot].n=i+n;
    for(int i=1;i<=n;i++)a[i].p=p[i]=(P){F(),F()},a[i].n=i;
    for(int x,y,v;m--;){
        x=F(),y=F(),v=F();
        e[++et]=(E){y,v,la[x]},la[x]=et;
        e[++et]=(E){x,v,la[y]},la[y]=et;
    }
    for(int i=1;i<=n;i++)sort_edge(i);
    for(int i=2;i<=et;i++)if(!vis[i])get_area(++col,i);
    for(int i=1;i<=col;i++)if(sum[inf]<sum[i])inf=i;
    for(int i=2;i<=et;i+=2)G.add(vis[i],vis[i^1],e[i].v);
    tree.init();std::sort(a+1,a+1+tot,cmp);
    for(int i=1;i<=tot;i++)
    if(a[i].n<=n){
        for(int j=la[a[i].n];j;j=e[j].nxt)
        if(p[e[j].to].x<p[a[i].n].x)tree.del(j>>1);
        else if(p[a[i].n].x<p[e[j].to].x)tree.ins(p[a[i].n].x,j>>1);
    }
    else tree.query(a[i].n,a[i].p.x,a[i].p.y);
    G.s=col+1,G.t=inf;G.maxflow(t);
    for(int i=1;i<=t;i++)printf("%d\n",ans[i]);
}

  评论这张
 
阅读(35)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018