传送门

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

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

#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;
}