bzoj2960: 跨平面

Description

Input

　第一行两个整数n和m，表示点与线段的数目。
　　接下来n行，每行两个整数x和y，表示第i个点的坐标，点从1到n编号。
　　接下来m行，每行四个整数p,q,V1和V2，表示存在一条从第p个点连向第q个点的线段，激活p->q这个方向的费用为V1，另一个方向费用为V2。
　　保证若两条线段相交，则交点是它们的公共端点。

Output

　　输出一行一个正整数，表示最小总激活费用。

转对偶图然后求任意根的最小树形图

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
const int inf=1000000;
int xs[3007],ys[3007];
struct edge{
    int fr;
    double a;
    int i1,i2,v;
    bool operator<(const edge&e)const{return fr!=e.fr?fr<e.fr:a<e.a;}
}e[6007];
int n,m,f[6007],id[6007],idp=0,E[1007][1007],fa[1007],ss[1007],sp=0,in[1007],q[1007];
bool d[1007];
int gf(int x){
    while(x!=f[x])x=f[x]=f[f[x]];
    return x;
}
void mins(int&a,int b){if(a>b)a=b;}
void ae(int a,int b,int c){mins(E[a][b],c);}
void cal(int w){
    fa[w]=0;
    d[w]=0;
    F(i,1,idp)if(d[i]&&(!fa[w]||E[w][i]<E[w][fa[w]]))fa[w]=i;
    d[w]=1;
}
int main(){
    scanf("%d%d",&n,&m);
    F(i,1,n)scanf("%d%d",xs+i,ys+i);
    F(i,1,m){
        int a,b,v1,v2;
        scanf("%d%d%d%d",&a,&b,&v1,&v2);
        if(!v1)v1=inf;
        if(!v2)v2=inf;
        e[i]=(edge){a,atan2(ys[b]-ys[a],xs[b]-xs[a]),i,i+m,v1};
        e[i+m]=(edge){b,atan2(ys[a]-ys[b],xs[a]-xs[b]),i+m,i,v2};
    }
    m*=2;
    std::sort(e+1,e+m+1);
    F(i,1,m)f[i]=i;
    for(int i=1,j=1;i<=m;i=j){
        for(;j<=m&&e[i].fr==e[j].fr;++j);
        f[gf(e[i].i1)]=gf(e[j-1].i2);
        for(++i;i<j;++i)f[gf(e[i].i1)]=gf(e[i-1].i2);
    }
    F(i,1,m)if(f[i]==i)id[i]=++idp;
    F(i,1,idp)F(j,1,idp)E[i][j]=inf;
    F(i,1,m)ae(id[gf(e[i].i1)],id[gf(e[i].i2)],e[i].v);
    F(i,0,idp)d[i]=1;
    F(i,1,idp)cal(i);
    int ans=0;
    while(1){
        int ql=0,qr=0;
        F(i,1,idp)in[i]=0;
        F(i,1,idp)if(d[i])++in[fa[i]];
        F(i,1,idp)if(d[i]&&!in[i])q[++qr]=i;
        in[0]=-1;
        while(ql!=qr){
            int f=fa[q[++ql]];
            if(!--in[f])q[++qr]=f;
        }
        sp=0;
        F(i,1,idp)if(in[i]){
            for(int w=i;in[w];in[w]=0,ss[++sp]=w,w=fa[w]);
            F(j,2,sp)d[ss[j]]=0;
            F(j,1,sp){
                int w=ss[j],dec=E[w][fa[w]];
                ans+=dec;
                F(k,0,idp)if(d[i])E[w][k]-=dec;
            }
            F(j,2,sp){
                int w=ss[j];
                F(k,0,idp)if(d[k]){
                    mins(E[k][i],E[k][w]);
                    mins(E[i][k],E[w][k]);
                }
            }
            F(j,1,idp)if(d[j]&&(!d[fa[j]]||E[j][i]<E[j][fa[j]]))fa[j]=i;
            cal(i);
            break;
        }
        if(!sp)break;
    }
    F(i,1,idp)if(d[i])ans+=E[i][fa[i]];
    printf("%d
",ans);
    return 0;
}