bzoj 2539: [Ctsc2000]丘比特的烦恼

.

题意：二分图最大匹配。
题解：费用流。
坑点都在discuss里了。
代码：

#include<bits/stdc++.h>
using namespace std;
int k,n,s,t;
struct person
{
    string name;
    int x,y,gen;
}a[70];
struct edge
{
    int x,y,c,d;
    edge *n,*o;
    edge(int x,int y,int c,int d,edge *n):x(x),y(y),c(c),d(d),n(n){}
}*fst[70],*pre[70];
map<string,int>re;
int mp[70][70],dis[70],v[70],flo[70],ans=0;
// vector<edge*>hh;
int multi(person p0,person p1,person p2)
{
    int x1=p1.x-p0.x,x2=p2.x-p0.x,y1=p1.y-p0.y,y2=p2.y-p0.y;
    return x1*y2-x2*y1;
}
int dis2(person x,person y)
{
    return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
void lower(string &x)
{
    for(string::iterator it=x.begin();it!=x.end();it++)
    if(*it<='Z')
    *it=*it-'A'+'a';
}
void gen(int x)
{
    static queue<int>q;
    q.push(x);
    a[x].gen=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(mp[x][i]!=0xc1c1c1c1&&a[i].gen==-1)
            {
                a[i].gen=a[x].gen^1;
                q.push(i);
            }
        }
    }
}
bool conn(int x,int y)
{
    if(dis2(a[x],a[y])>k*k)
    return 0;
    pair<int,int>xr=make_pair(a[x].x,a[y].x),yr=make_pair(a[x].y,a[y].y);
    if(xr.first>xr.second)
    swap(xr.first,xr.second);
    if(yr.first>yr.second)
    swap(yr.first,yr.second);
    for(int i=1;i<=n;i++)
    {
        if(i==x||i==y)
        continue;
        if(a[i].x>=xr.first&&a[i].x<=xr.second&&a[i].y>=yr.first&&a[i].y<=yr.second&&multi(a[i],a[x],a[y])==0)
        return 0;
    }
    return 1;
}
void ins(int x,int y,int c,int d)
{
    edge *p1=new edge(x,y,c,d,fst[x]);
    edge *p2=new edge(y,x,-c,0,fst[y]);
    p1->o=p2;
    p2->o=p1;
    fst[x]=p1;
    fst[y]=p2;/*
    hh.push_back(p1);
    hh.push_back(p2);*/
}
int spfa()
{
    memset(dis,-63,sizeof(dis));
    memset(v,0,sizeof(v));
    memset(pre,0,sizeof(pre));
    memset(flo,0,sizeof(flo));
    static queue<int>q;
    q.push(s);
    v[s]=1;
    flo[s]=1<<30;
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        v[x]=0;
        for(edge *i=fst[x];i;i=i->n)
        {
            int y=i->y;
            if(i->d&&dis[y]<dis[x]+i->c)
            {
                dis[y]=dis[x]+i->c;
                flo[y]=min(i->d,flo[x]);
                pre[y]=i;
                if(!v[y])
                {
                    v[y]=1;
                    q.push(y);
                }
            }
        }
    }
    return flo[t];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>k>>n;
    n<<=1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].name;
        lower(a[i].name);
        re[a[i].name]=i;
        a[i].gen=-1;
    }
    memset(mp,-63,sizeof(mp));
    while(1)
    {
        string s1,s2;
        cin>>s1;
        if(s1=="End")
        break;
        int k;
        cin>>s2>>k;
        lower(s1);
        lower(s2);
        mp[re[s1]][re[s2]]=mp[re[s2]][re[s1]]=k;
    }
    bool tf[70];
    memset(tf,0,sizeof(tf));
    for(int i=1;i<=n;i++)
    {
        if(a[i].gen==-1)
        gen(i);
    }/*
    for(int i=1;i<=n;i++)
    cout<<a[i].name<<' '<<a[i].gen<<endl;*/
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)
            continue;
            bool hh=conn(i,j);
            if(!hh)
            mp[i][j]=0xc1c1c1c1;
            else if(mp[i][j]==0xc1c1c1c1)
            mp[i][j]=1;
        }
    }/*
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        cout<<((mp[i][j]==0xc1c1c1c1)?string("-inf"):to_string(mp[i][j]))<<' ';
        cout<<endl;
    }*/
    s=0,t=n+1;
    for(int i=1;i<=n;i++)
    {
        if(a[i].gen)
        {
            ins(s,i,0,1);
            for(int j=1;j<=n;j++)
            if(!a[j].gen&&mp[i][j]!=0xc1c1c1c1)
            ins(i,j,mp[i][j],1);
        }
        else
        {
            ins(i,t,0,1);
        }
    }/*
    a[s].name="st";
    a[t].name="ed";
    for(auto i:hh)
    cout<<a[i->x].name<<' '<<a[i->y].name<<' '<<i->c<<' '<<i->d<<endl;*/
    int hh;
    while(hh=spfa())
    {
        for(edge *i=pre[t];i;i=pre[i->x])
        {
            i->d-=hh;
            i->o->d+=hh;
            ans+=hh*i->c;
        }
    }
    cout<<ans<<endl;
}