• 周日. 5月 26th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

BZOJ2965: 保护古迹

admin

11月 28, 2021

2965: 保护古迹

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 382  Solved: 163
[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个点互不相同。

 

思路{

  同样是平面图转对偶图后(基本平面图的划分算法顺便求出点所属的区域)p较小,

  可以直接枚举要保护的古迹,直接跑最小割都可以了用Inf排除不参与决策的边.

}

#include<bits/stdc++.h>
#define RG register
#define il inline 
#define N 10010
#define inf (1<<30)
#define LL long long
#define db double
using namespace std;
struct ed{int nxt,to,c;}e[N*2];
int head[N],tot,dep[N];
void clear(){memset(head,-1,sizeof(head));tot=0;}
void link(int u,int v,int c){e[tot].nxt=head[u];e[tot].to=v;e[tot].c=c;head[u]=tot++;}
void LINK(int u,int v,int c){link(u,v,c),link(v,u,c);}
bool BFS(int s,int t){
  queue<int>que;
  while(!que.empty())que.pop();
  memset(dep,0,sizeof(dep));
  dep[s]=1;que.push(s);
  while(!que.empty()){
    int u=que.front();que.pop();
    for(int i=head[u];i!=-1;i=e[i].nxt){
      int v=e[i].to;if(!dep[v]&&e[i].c){
    dep[v]=dep[u]+1;
    if(v==t)return true;
    que.push(v);
      }
    }
  }return false;
}
int dinic(int s,int t,int T){
  if(s==t)return T;int tag(0);
  for(int i=head[s];i!=-1;i=e[i].nxt)if(dep[e[i].to]==dep[s]+1&&e[i].c){
      int v=e[i].to;
      int d=dinic(v,t,min(T-tag,e[i].c));
      e[i].c-=d,e[i^1].c+=d;tag+=d;
      if(tag==T)break;
    }if(!tag)dep[s]=0;return tag;
}
int maxflow(int s,int t){
  int flow(0);
  while(BFS(s,t))flow+=dinic(s,t,inf);
  return flow;
}
 
struct point{
  db x,y;
  point() {}
  point(db X,db Y):x(X),y(Y) {}
  point operator +(const point & a)const{return point(x+a.x,y+a.y);}
  point operator -(const point & a)const{return point(x-a.x,y-a.y);}
  point operator *(const db & k)const{return point(x*k,y*k);}
  db operator *(const point & a)const{return x*a.y-y*a.x;}
  db len(){return x*x+y*y;}
  void read(){scanf("%lf%lf",&x,&y);}
}p[N],a[N];
struct Line{
  point st,v;
  int fir,to;
  int flag,val;
  db k;
  Line * re;
  Line() {}
  Line(point a,point b,int F,int T,int d):st(a),v(b),fir(F),to(T),val(d) {
    flag=0;
    k=atan2(v.y,v.x);
  }
}l[N];
 
bool Comp(Line *l1,Line *l2){return l1->k<l2->k;}
vector<Line *>ex[N];
int sum,n,m,idn,BL[N];bool vis[N];
bool check(Line *l1,point p){
  return (l1->v*(p-l1->st))>0;
}
bool BZ[N];
void find(Line *l1){
  memset(vis,true,sizeof(vis));
  for(int i=1;i<=sum;++i)if(vis[i])vis[i]=!check(l1,a[i]);
  int sta=l1->fir,now=l1->to;
  db s=p[l1->fir]*p[l1->to];l1->flag=idn;
  do{
    vector<Line * >::iterator it=upper_bound(ex[now].begin(),ex[now].end(),l1->re,Comp);
    if(it==ex[now].end())
      it=ex[now].begin();
    l1=*it;
    now=l1->to;l1->flag=idn;
    l1->flag=idn;s+=p[l1->fir]*p[l1->to];
    for(int i=1;i<=sum;++i)if(vis[i])vis[i]=!check(l1,a[i]);
  }while(now!=sta);
  for(int i=1;i<=sum;++i)if(vis[i])BL[i]=idn;
  if(s>0)BZ[idn]=true;
}
int T=1100;int ans[N];
struct edge{
  int fir,to,len;
  edge() {}
  edge(int F,int To,int W):fir(F),to(To),len(W) {
    if(BZ[F])fir=T;
    if(BZ[To])to=T;
  }
}E[N];int sig;
int build(int x){
  int num(0);clear();
  for(int i=1;i<=sum;++i){
    if((x>>(i-1))&1){
      LINK(0,BL[i],inf);
      num++;
    }
  }
  for(int i=1;i<=sig;++i)LINK(E[i].fir,E[i].to,E[i].len);
  return num;
}
int main(){
  scanf("%d%d%d",&sum,&n,&m);
  for(int i=1;i<=sum;++i)a[i].read();
  for(int i=1;i<=n;++i)p[i].read();
  for(int i=1;i<=m;++i){
    int x,y,w;scanf("%d%d%d",&x,&y,&w);
    l[(i<<1)-1]=Line(p[x],p[y]-p[x],x,y,w);
    l[(i<<1)]=Line(p[y],p[x]-p[y],y,x,w);
    l[(i<<1)-1].re=&l[(i<<1)];
    l[(i<<1)].re=&l[(i<<1)-1];
    ex[x].push_back(&l[(i<<1)-1]);
    ex[y].push_back(&l[(i<<1)]);
  }
  for(int i=1;i<=n;++i)sort(ex[i].begin(),ex[i].end(),Comp);
  for(int i=1;i<=2*m;++i)if(!l[i].flag)idn++,find(&l[i]);
  for(int i=1;i<=2*m;i+=2)
    E[++sig]=edge(l[i].flag,l[i+1].flag,l[i].val);
  memset(ans,127/3,sizeof(ans));
  for(int i=1;i<(1<<sum);++i){
    int cnt=build(i);
    ans[cnt]=min(ans[cnt],maxflow(0,T));
  }
  for(int i=1;i<=sum;++i)
    cout<<ans[i]<<"
";
  return 0;
}

《BZOJ2965: 保护古迹》有一个想法
  1. Wow, fantastic blog layout! How long have you ever been running a blog for?
    you made blogging glance easy. The entire look of your web site is excellent, as well as
    the content material! You can see similar here sklep online

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注