喵。

Problem

给出一张被划分出多个区域的平面图。区域染不同颜色会有不同的权值，如果相邻两区域颜色不同会产生额外费用。求最大贡献。

Solution

前置知识比较多？

极角排序和最左转线。极角排序可以用函数 atan2(y, x) 求出 $\arctan \frac{y}{x}$ ，返回 $[-\pi, \pi]$ 的结果。如果小于零就加上个 $2\pi$ 吧，然后排序就行了。

因为有可能被卡精度，你也可以用象限排序。如果同一象限就叉积，否则比象限。太难打就没打了。

然后最左转线用于求这种带坐标的平面图和对偶图转化。具体请参见 miskcoo’s Blog ，这里讲得比较好，代码也写得很好。

就是细节不少。

然后我们发现题面的意思其实只需要我们求一种匹配方案使得 W 和 B 还有相邻产生的总贡献量最小，然后用 W 和 B 的总值减去这个值即可。

网络流嘛。随便跑跑。

Code

// Code by ajcxsu
// Problem: everfeel

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

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(!isdigit(ch)) pl=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=4e4+10, M=4e5+10;
struct P {
    int x, y;
    P operator + (P b) { return {x+b.x, y+b.y}; }
    P operator - (P b) { return {x-b.x, y-b.y}; }
    double ang() { double ang=atan2(y, x); if(ang<0) ang+=2.0*M_PI; return ang;}
} p[N];
struct Edge {
    int w, u, v; 
    double ang;
} e[M];
vector<int> to[N];
int tp[N];
int ridx, mp;
int a[N], b[N], rk[M], bel[M];
int A[M], B[M], tot;
void ins(int a, int b, int w) {
    e[mp++]={w, a, b, (p[b]-p[a]).ang()};
}

namespace NS {
    const int s=N-1, t=N-2;
    int h[N], to[M], nexp[M], W[M], p=2;
    inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
    #define sins(x, y, z) ins(x, y, z), ins(y, x, 0)
    int fl[N];
    bool bfs() {
        queue<int> qu; qu.push(s); memset(fl, 0, sizeof(fl)); fl[s]=1;
        while(!qu.empty()) {
            int na=qu.front(); qu.pop();
            for(int u=h[na];u;u=nexp[u])
                if(W[u] && !fl[to[u]]) fl[to[u]]=fl[na]+1, qu.push(to[u]);
        }
        return fl[t];
    }
    #define INF (0x3f3f3f3f)
    int dfs(int x, int op) {
        if(x==t) return op;
        int flow=0;
        for(int u=h[x];u;u=nexp[u])
            if(W[u] && fl[to[u]]==fl[x]+1) {
                int d=dfs(to[u], min(op-flow, W[u]));
                W[u]-=d, W[u^1]+=d, flow+=d;
                if(flow==op) break;
            }
        if(!flow) fl[x]=0;
        return flow;
    }
    void work() {
        for(int i=0; i<mp; i+=2)
            ins(bel[i], bel[i+1], e[i].w), ins(bel[i+1], bel[i], e[i].w);
        for(int i=1; i<=ridx; i++)
            sins(s, i, A[i]), sins(i, t, B[i]), tot+=A[i]+B[i];
        int flow=0;
        while(bfs()) flow+=dfs(s, INF);
        printf("%d\n", tot-flow);
    }
}

bool vis[N];
void findreg(int x, int eid) {
    if(vis[eid]) return;
    ++ridx;
    while(!vis[eid]) {
        vis[eid]=1;
        bel[eid]=ridx, x=e[eid].v;
        A[ridx]+=a[x], B[ridx]+=b[x];
        if(!rk[eid^1]) eid=to[x].back();
        else eid=to[x][rk[eid^1]-1];
    }
}


int main() {
    #ifndef LOCAL
    freopen("everfeel.in","r",stdin);
    freopen("everfeel.out","w",stdout);
    #endif
    int num; gn(num);
    int n, m; gn(n), gn(m);
    int u, v, w;
    for(int i=1; i<=n; i++) gn(u), gn(v), p[i]={u, v}, gn(a[i]), gn(b[i]);
    vector<pair<double, int> > tmp;
    for(int i=1; i<=m; i++) {
        gn(u), gn(v), gn(w);
        ins(u, v, w);
        ins(v, u, w);
    }
    
    for(int i=0; i<mp; i++) tmp.push_back(make_pair(e[i].ang, i));
    sort(tmp.begin(), tmp.end());
    for(int i=0; i<mp; i++) {
        int eid=tmp[i].second;
        rk[eid]=to[e[eid].u].size();
        to[e[eid].u].push_back(eid);
    }
    for(int i=1; i<=n; i++)
        for(int j=0; j<to[i].size(); j++)
            findreg(i, to[i][j]);
    NS::work();
    return 0;
}