[PA2014]Muzeum-白红宇

[PA2014]Muzeum

阅读量：5878 次

发布时间：2019-06-19

本文共 2901 字，大约阅读时间需要 9 分钟。

传送门

Solution

显然这是一个最大权闭合子图的问题,所以你把图建出来跑网络流就是\(50pts\).

接着你旋转坐标系然后把这个转换成为一个贪心替换网络流的问题,然后就是一个\(set\)的事了.

代码实现

/*  mail: mleautomaton@foxmail.com  author: MLEAutoMaton  This Code is made by MLEAutoMaton*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=5010,Inf=1e9+10;struct thing{ int x,y,v;}p[N],q[N];int n,m,w,h,front[N],cnt,s,t,dep[N];struct node{ int to,nxt,w;}e[6000010];void Add(int u,int v,int w){e[cnt]=(node){v,front[u],w};front[u]=cnt++;e[cnt]=(node){u,front[v],0};front[v]=cnt++;}queue
             
              Q;bool bfs(){ Q.push(s);memset(dep,0,sizeof(dep));dep[s]=1; while(!Q.empty()) { int u=Q.front();Q.pop(); for(int i=front[u];i!=-1;i=e[i].nxt) { int v=e[i].to; if(!dep[v] && e[i].w) { dep[v]=dep[u]+1; Q.push(v); } } } return dep[t];}int dfs(int u,int flow){ if(u==t || !flow)return flow; for(int i=front[u];i!=-1;i=e[i].nxt) { int v=e[i].to; if(dep[v]==dep[u]+1 && e[i].w) { int di=dfs(v,min(flow,e[i].w)); if(di) { e[i].w-=di;e[i^1].w+=di; return di; } else dep[v]=0; } } return 0;}int Dinic(){ int flow=0; while(bfs()) while(int d=dfs(s,Inf)) flow+=d; return flow;}bool bein(int i,int j){return 1ll*abs(p[j].x-q[i].x)*h<=1ll*w*abs(p[j].y-q[i].y);}namespace Accepted{ #define int ll const int N=500010; struct node { int x,y,v; bool operator<(const node b)const{return x
              
                pii; set
               
                se; #define mp make_pair void main() { n=gi();m=gi();w=gi();h=gi();int ans=0; for(int i=1;i<=n;i++){int x=1ll*gi()*h,y=1ll*gi()*w,v=gi();p[i].x=x+y;p[i].y=x-y;p[i].v=v;ans+=v;} for(int i=1;i<=m;i++){int x=1ll*gi()*h,y=1ll*gi()*w,v=gi();q[i].x=x+y;q[i].y=x-y;q[i].v=v;} sort(p+1,p+n+1); sort(q+1,q+m+1); int pos=1; for(int i=1;i<=m;i++) { while(pos<=n && p[pos].x<=q[i].x)se.insert(mp(p[pos].y,p[pos].v)),pos++; set
                
                 ::iterator it=se.lower_bound(mp(q[i].y,0));int flow=q[i].v; while(flow && it!=se.end()) { pii now=*it;se.erase(it); int d=min(flow,now.second); now.second-=d;ans-=d;flow-=d; if(now.second)se.insert(now); else it=se.lower_bound(mp(q[i].y,0)); } } printf("%lld\n",ans); return; }}signed main(){/* ll ans=0; n=gi();m=gi();memset(front,-1,sizeof(front));s=0;t=n+m+1; w=gi();h=gi(); for(int i=1;i<=n;i++)p[i].x=gi(),p[i].y=gi(),p[i].v=gi(),Add(s,i,p[i].v),ans+=p[i].v; for(int i=1;i<=m;i++)q[i].x=gi(),q[i].y=gi(),q[i].v=gi(),Add(i+n,t,q[i].v); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(q[i].y>=p[j].y && bein(i,j))Add(j,i+n,Inf); printf("%lld\n",ans-Dinic());*/ Accepted::main(); return 0;}