ZJT's Blog

大変に気分がいい~

[BZOJ 2965] 保护古迹

2018-1-21 1:02018-1-21 13:38
BZOJ平面图网络流最小割

传送门

建出平面图的对偶图之后,枚举古迹的子集跑最小割就行了。

因为这题范围很小,点定位可以直接暴力枚举判断,所以还是比较好写的。

#include <bits/stdc++.h>
#define MAXN 10010
#define MAXM 100000
using namespace std;

const double eps=1e-6;

struct vec{
    double x,y;
    vec(double _x=0,double _y=0):x(_x),y(_y){}
    friend vec operator-(vec x,vec y){ return vec(x.x-y.x,x.y-y.y); }
    friend double cross(vec x,vec y){ return x.x*y.y-x.y*y.x; }
    double angle(){
        double res=atan2(y,x); 
        if(res<0) res+=2*M_PI;
        return res;
    }
}p[MAXN],qp[MAXN];

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[MAXM];

int n,m,q,numc;
vector<pair<int,int> > ep[MAXN];
vector<bool> ve[MAXN];
int e2[MAXM][3],et[MAXM][2],cur;
vector<int> ec[MAXM];
int pos[MAXN];
double ca[MAXM];
int g[MAXN],nume;
int level[MAXN],cure[MAXN],S,T;
int ans[MAXN];

void addEdge(int u,int v,int w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
    e[nume]=edge(u,g[v],0);
    g[v]=nume++;
}

bool cmp(pair<int,int> x,pair<int,int> y){
    return (p[x.first]-p[cur]).angle()>(p[y.first]-p[cur]).angle();
}

void pre_gao(int x){
    cur=x;
    sort(ep[x].begin(),ep[x].end(),cmp);
    ve[x].resize(ep[x].size());
}

void build(int x){
    int c=++numc;
    int x0=x,x1,ce;
    double area=0;
    for(int i=0;i<ep[x].size();i++)
        if(!ve[x][i]){
            x1=ep[x][i].first,ce=ep[x][i].second,ve[x][i]=1;
            break;
        }
    if(!et[ce][0]) et[ce][0]=c;
    else et[ce][1]=c;
    ec[c].push_back(ce);
    while(x1!=x0){
        int temp;
        for(int i=0;i<ep[x1].size();i++)
            if(ep[x1][i].first==x) temp=i;
        temp=(temp+1)%ep[x1].size();
        while(ve[x1][temp]) temp=(temp+1)%ep[x1].size();
        int x2=ep[x1][temp].first;
        ce=ep[x1][temp].second;
        ve[x1][temp]=1;
        x=x1;
        x1=x2;
        if(!et[ce][0]) et[ce][0]=c;
        else et[ce][1]=c;
        ec[c].push_back(ce);
        area+=cross(p[x]-p[x0],p[x1]-p[x]);
    }
    ca[c]=area;
}

bool locate(int x,int y){
    int cnt=0;
    for(int i=0;i<ec[y].size();i++){
        int u=e2[ec[y][i]][0],v=e2[ec[y][i]][1];
        if(p[u].y>p[v].y) swap(u,v);
        if(qp[x].y<p[u].y+eps || qp[x].y>p[v].y-eps) continue;
        double x1=p[u].x+(p[v].x-p[u].x)*(qp[x].y-p[u].y)/(p[v].y-p[u].y);
        if(x1>qp[x].x) cnt++;
    }
    return cnt&1;
}

void build(){
    int x;
    while(1){
        x=0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<ep[i].size();j++)
                if(!ve[i][j])
                    x=i;
        if(!x) break;
        build(x);
    }
    for(int i=1;i<=q;i++)
        for(int j=1;j<=numc;j++)
            if(ca[j]>0 && locate(i,j)) pos[i]=j;
}

bool bfs(){
    static queue<int> Q;
    for(int i=1;i<=numc;i++)
        level[i]=-1,cure[i]=g[i];
    Q.push(S);
    level[S]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=g[x];~i;i=e[i].next)
            if(e[i].w && level[e[i].to]==-1){
                level[e[i].to]=level[x]+1;
                Q.push(e[i].to);
            }
    }
    return level[T]!=-1;
}

int dfs(int x,int delta){
    if(x==T) return delta;
    int res=0;
    for(int &i=cure[x];~i;i=e[i].next)
        if(e[i].w && level[e[i].to]==level[x]+1){
            int temp=dfs(e[i].to,min(delta,e[i].w));
            e[i].w-=temp;
            e[i^1].w+=temp;
            delta-=temp;
            res+=temp;
            if(!delta) return res;
        }
    return res;
}

int query(int mask){
    int res=0;
    for(int i=1;i<=numc;i++) g[i]=-1;
    nume=0;
    for(int i=1;i<=q;i++)
        if(mask&(1<<(i-1)))
            addEdge(S,pos[i],0x7FFFFFFF);
    for(int i=1;i<=m;i++){
        addEdge(et[i][0],et[i][1],e2[i][2]);
        addEdge(et[i][1],et[i][0],e2[i][2]);
    }
    while(bfs()) res+=dfs(S,0x7FFFFFFF);
    return res;
}

int main(){
#ifdef DEBUG
    freopen("in","r",stdin);
#endif
    scanf("%d%d%d",&q,&n,&m);
    for(int i=1;i<=q;i++) scanf("%lf%lf",&qp[i].x,&qp[i].y);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e2[i][0]=u; e2[i][1]=v; e2[i][2]=w;
        ep[u].push_back(make_pair(v,i));
        ep[v].push_back(make_pair(u,i));
    }
    for(int i=1;i<=n;i++) pre_gao(i);
    build();
    for(int i=1;i<=numc;i++)
        if(ca[i]<0) T=i;
    for(int i=1;i<=q;i++) ans[i]=0x7FFFFFFF;
    S=++numc;
    int maxs=1<<q;
    for(int i=1;i<maxs;i++){
        int cnt=0;
        for(int j=1;j<=i;j<<=1)
            if(i&j) cnt++;
        ans[cnt]=min(ans[cnt],query(i));
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}

查看详细内容

[BZOJ 3774] 最优选择

2018-1-20 18:342018-1-20 18:34
网络流最小割BZOJ

传送门

这题建模的关键在于要把每个点的收益拆成两份考虑。第一份是控制这个点带来的收益(获得这种收益的同时也要付出代价),第二份是这个点周围的点都被控制时的收益(获得这种收益的同时一定不会获得第一份收益)。

我们对网格图黑白染色,钦定黑色点划到S集代表被控制,白色点划到T集代表被控制。这样,一个黑色点能获得第二份收益,当且仅当他自己被划分到T集,且周围几个点都被划到T集(这代表了这个点没有获得第一份收益,且周围几个点都被控制)。白色点也类似,自己和周围的点都要划到S集才能得到第二份收益。我们对于每个点的第二份收益再开一个新点,这样就不难建出最小割模型了。

#include <bits/stdc++.h>
#define MAXN 5010
#define MAXM 60
#define INF 0x77777777
using namespace std;

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[1000000];

int n,m;
int a[MAXM][MAXM],b[MAXM][MAXM];
int p1[MAXM][MAXM],p2[MAXM][MAXM],S,T,nump;
int cur[MAXN],level[MAXN];
int g[MAXN],nume;

bool bfs(){
    static queue<int> Q;
    for(int i=1;i<=nump;i++) cur[i]=g[i],level[i]=-1;
    Q.push(S);
    level[S]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=g[x];~i;i=e[i].next)
            if(e[i].w && level[e[i].to]==-1){
                level[e[i].to]=level[x]+1;
                Q.push(e[i].to);
            }
    }
    return level[T]!=-1;
}

int dfs(int x,int delta){
    if(x==T) return delta;
    int res=0;
    for(int &i=cur[x];~i;i=e[i].next)
        if(e[i].w && level[e[i].to]==level[x]+1){
            int temp=dfs(e[i].to,min(delta,e[i].w));
            e[i].w-=temp;
            e[i^1].w+=temp;
            res+=temp;
            delta-=temp;
            if(!delta) return res;
        }
    return res;
}

void addEdge(int u,int v,int w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
    e[nume]=edge(u,g[v],0);
    g[v]=nume++;
}

int main(){
#ifdef DEBUG
    freopen("in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&m);
    int ans=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&b[i][j]),ans+=2*b[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) p1[i][j]=++nump,p2[i][j]=++nump;
    S=++nump; T=++nump;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if((i+j)&1){
                addEdge(S,p1[i][j],a[i][j]);
                addEdge(p1[i][j],T,b[i][j]);
                addEdge(S,p2[i][j],b[i][j]);
                addEdge(p2[i][j],p1[i][j],INF);
                if(i>1) addEdge(p2[i][j],p1[i-1][j],INF);
                if(j>1) addEdge(p2[i][j],p1[i][j-1],INF);
                if(i<n) addEdge(p2[i][j],p1[i+1][j],INF);
                if(j<m) addEdge(p2[i][j],p1[i][j+1],INF);
            }else{
                addEdge(S,p1[i][j],b[i][j]);
                addEdge(p1[i][j],T,a[i][j]);
                addEdge(p2[i][j],T,b[i][j]);
                addEdge(p1[i][j],p2[i][j],INF);
                if(i>1) addEdge(p1[i-1][j],p2[i][j],INF);
                if(j>1) addEdge(p1[i][j-1],p2[i][j],INF);
                if(i<n) addEdge(p1[i+1][j],p2[i][j],INF);
                if(j<m) addEdge(p1[i][j+1],p2[i][j],INF);
            }
    while(bfs()) 
        ans-=dfs(S,INF);
    printf("%d\n",ans);
    return 0;
}

查看详细内容

[BZOJ 4788] [CERC2016] Bipartite Blanket

2018-1-16 15:192018-1-16 15:19
BZOJHall定理结论题

传送门

这题需要一个引理:一个点集$C=A\cup B$($A$为左边的点集,$B$为右边的点集)能被某个匹配覆盖,当且仅当$A$与右边的某个大小相等的点集$A'$之间存在完美匹配,且$B$与左边的某个大小相等的点集$B'$之间存在完美匹配。

证明大概是这样的:我们构造一个有向图,对于$A$到$A'$之间的匹配,我们从左往右连边,对于$B$到$B'$的匹配,我们从右往左连边。由于每个点入度、出度都至多为$1$,所以这个有向图一定是由一些环和链组成的。环的话一定是偶环,我们每两个点连一条匹配边就行了。链的末端一定不在$C$中,如果链长是偶数就两两连边,否则就可以不管最后一个点了。

有这个引理就好做了,我们直接用Hall定理判断两边点集的每一个子集符不符合引理的条件,然后把所有符合条件的排个序,双指针扫一遍就行了。

#include <bits/stdc++.h>
#define MAXN 30
#define MAXS 1100000
#define LL long long
#define lowbit(x) (x&(-x))
using namespace std;

int n,m;
int g[MAXN][MAXN];
int v1[MAXN],v2[MAXN],lim;
vector<int> s1,s2;

void gao1(){
    static int t[MAXN],h[MAXS],f[MAXS],s[MAXS];
    for(int i=1;i<=n;i++){
        t[i]=0;
        for(int j=1;j<=m;j++)
            if(g[i][j]) t[i]|=1<<(j-1);
    }
    s[0]=h[0]=0; f[0]=1;
    int maxs=1<<n;
    for(int i=1;i<maxs;i++){
        f[i]=1;
        s[i]=0;
        int c1=0,c2=0;
        for(int j=1;j<=n;j++)
            if(i&(1<<(j-1))){
                h[i]=h[i^(1<<(j-1))]|t[j];
                if(!f[i^(1<<(j-1))]) f[i]=0;
                s[i]+=v1[j];
                c1++;
            }
        for(int j=1;j<=m;j++)
            if(h[i]&(1<<(j-1)))
                c2++;
        if(c2<c1) f[i]=0;
    }
    for(int i=0;i<maxs;i++) if(f[i]) s1.push_back(s[i]);
}

void gao2(){
    static int t[MAXN],h[MAXS],f[MAXS],s[MAXS];
    for(int i=1;i<=m;i++){
        t[i]=0;
        for(int j=1;j<=n;j++)
            if(g[j][i]) t[i]|=1<<(j-1);
    }
    s[0]=h[0]=0; f[0]=1;
    int maxs=1<<m;
    for(int i=1;i<maxs;i++){
        f[i]=1;
        s[i]=0;
        int c1=0,c2=0;
        for(int j=1;j<=m;j++)
            if(i&(1<<(j-1))){
                h[i]=h[i^(1<<(j-1))]|t[j];
                if(!f[i^(1<<(j-1))]) f[i]=0;
                s[i]+=v2[j];
                c1++;
            }
        for(int j=1;j<=n;j++)
            if(h[i]&(1<<(j-1)))
                c2++;
        if(c2<c1) f[i]=0;
    }
    for(int i=0;i<maxs;i++) if(f[i]) s2.push_back(s[i]);
}

int main(){
#ifdef DEBUG
    freopen("4788.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        static char str[MAXN];
        scanf("%s",str+1);
        for(int j=1;j<=m;j++) g[i][j]=(str[j]=='1');
    }
    for(int i=1;i<=n;i++) scanf("%d",v1+i);
    for(int i=1;i<=m;i++) scanf("%d",v2+i);
    scanf("%d",&lim);
    gao1();
    gao2();
    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());
    LL ans=0;
    int now=s2.size()-1;
    for(int i=0;i<s1.size();i++){
        while(now>=0 && s1[i]+s2[now]>=lim) now--;
        ans+=s2.size()-1-now;
    }
    printf("%lld\n",ans);
    return 0;
}

查看详细内容

[BZOJ 3564] [SHOI2014] 信号增幅仪

2018-1-13 16:552018-1-13 16:55
BZOJ计算几何最小圆覆盖

传送门

也是模板题,不过要把所有点在一个方向上进行缩放,正交分解一下就行了。

#include <bits/stdc++.h>
#define MAXN 50010
using namespace std;

const double eps=1e-6;

struct vec{
    double x,y;
    vec(double _x=0,double _y=0):x(_x),y(_y){}
    friend vec operator*(vec x,double y){ return vec(x.x*y,x.y*y); }
    friend vec operator+(vec x,vec y){ return vec(x.x+y.x,x.y+y.y); }
    friend vec operator-(vec x,vec y){ return vec(x.x-y.x,x.y-y.y); }
    friend double dot(vec x,vec y){ return x.x*y.x+x.y*y.y; }
    friend double cross(vec x,vec y){ return x.x*y.y-x.y*y.x; }
    friend double dis(vec x,vec y){ return sqrt(dot(x-y,x-y)); }
}a[MAXN];

int n;
double rot,scale;

vec pre_gao(vec x){
    vec axis(cos(rot),sin(rot));
    vec x1=axis*dot(axis,x);
    vec x2=x-x1;
    return x1*(1./scale)+x2;
}

vec get_inter(vec s1,vec d1,vec s2,vec d2){
    double det=cross(d1,d2);
    vec t=vec(d2.y,-d2.x)*(1./det);
    double x=-dot(s1-s2,t);
    return s1+d1*x;
}

vec get_center(vec a,vec b,vec c,double &r){
    vec d=b+(c-b)*.5,e=a+(c-a)*.5;
    vec d1((c-b).y,-(c-b).x),e1((c-a).y,-(c-a).x);
    vec res=get_inter(d,d1,e,e1);
    r=max(max(dis(res,a),dis(res,b)),dis(res,c));
    return res;
}

vec gao3(int x,int y,double &r){
    vec c=a[x]+(a[y]-a[x])*.5;
    r=dis(a[x],a[y])/2;
    for(int i=1;i<x;i++){
        if(dis(a[i],c)<r+eps) continue;
        c=get_center(a[i],a[x],a[y],r);
    }
    return c;
}

vec gao2(int x,double &r){
    vec c=a[x];
    r=0;
    for(int i=1;i<x;i++){
        if(dis(a[i],c)<r+eps) continue;
        c=gao3(i,x,r);
    }
    return c;
}

vec gao1(double &r){
    vec c=a[1];
    r=0;
    for(int i=2;i<=n;i++){
        if(dis(a[i],c)<r+eps) continue;
        c=gao2(i,r);
    }
    return c;
}

int main(){
#ifdef DEBUG
    freopen("in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
    scanf("%lf%lf",&rot,&scale);
    rot=rot*M_PI/180.;
    for(int i=1;i<=n;i++) a[i]=pre_gao(a[i]);
    random_shuffle(a+1,a+n+1);
    double res;
    gao1(res);
    printf("%.3lf\n",res);
}

查看详细内容

[BZOJ 1336] [Balkan2002] Alien最小圆覆盖

2018-1-13 16:422018-1-13 16:42
BZOJ计算几何最小圆覆盖

传送门

愉快的模板题

1337也是

#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;

const double eps=1e-6;

struct vec{
    double x,y;
    vec(double _x=0,double _y=0):x(_x),y(_y){}
    friend vec operator*(vec x,double y){ return vec(x.x*y,x.y*y); }
    friend vec operator+(vec x,vec y){ return vec(x.x+y.x,x.y+y.y); }
    friend vec operator-(vec x,vec y){ return vec(x.x-y.x,x.y-y.y); }
    friend double dot(vec x,vec y){ return x.x*y.x+x.y*y.y; }
    friend double cross(vec x,vec y){ return x.x*y.y-x.y*y.x; }
    friend double dis(vec x,vec y){ return sqrt(dot(y-x,y-x)); }
}a[MAXN];

int n;

vec get_inter(vec s1,vec d1,vec s2,vec d2){
    double det=cross(d1,d2);
    vec t(d2.y/det,-d2.x/det);
    double x=dot(s2-s1,t);
    return s1+d1*x;
}

vec get_center(vec a,vec b,vec c,double &r){
    vec d=a+(b-a)*.5,d1((b-a).y,-(b-a).x);
    vec e=b+(c-b)*.5,e1((c-b).y,-(c-b).x);
    vec res=get_inter(d,d1,e,e1);
    r=dis(res,a);
    return res;
}

vec gao3(int x,int y,double &r){
    vec c=a[x]+(a[y]-a[x])*.5;
    r=dis(a[x],a[y])/2;
    for(int i=1;i<x;i++){
        if(dis(c,a[i])<r+eps) continue;
        c=get_center(a[i],a[x],a[y],r);
    }
    return c;
}

vec gao2(int x,double &r){
    vec c=a[x]; r=0;
    for(int i=1;i<x;i++){
        if(dis(c,a[i])<r+eps) continue;
        c=gao3(i,x,r);
    }
    return c;
}

vec gao1(double &r){
    vec c=a[1]; r=0;
    for(int i=2;i<=n;i++){
        if(dis(c,a[i])<r+eps) continue;
        c=gao2(i,r);
    }
    return c;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
    random_shuffle(a+1,a+n+1);
    double r;
    vec c=gao1(r);
    printf("%.10lf\n%.10lf %.10lf\n",r,c.x,c.y);
}

查看详细内容