P1500题解

· · 题解

思路：

写了个费用流，按二分图建边，费用就是缘分，跑最大费用最大流即可。 两个坑点：

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#define S n*2
#define T n*2+1
#define EPS 1e-6
using namespace std;
const int INF=1<<25;
//map存对应姓名和节点编号
map<string, int> m;
struct pos{
    int x, y;
    pos(int a, int b):x(a), y(b){}
    pos(){}
}v[60];
//边
struct node{
    int to, val, cost, flow; node *next, *rev;
    node(int t, int c, int f):to(t), cost(c), flow(f), next(NULL), rev(NULL){}
    node():to(0), cost(0), flow(0), next(NULL), rev(NULL){}
}*from[62];
//表
struct li{
    node *pre, *last;
    li():pre(NULL), last(NULL){}
    void push(int t, int c, int f){
        if(pre) last=last->next=new node(t, c, f);
        else pre=last=new node(t, c, f);
    }
}graph[62];
int k, n, karma[60][60], flow[62], cost[62], ans;
bool state[62];
//检查k是否在i、j线段上
bool check(double s1, int i, int j, int k){
    double s2=sqrt((v[k].x-v[j].x)*(v[k].x-v[j].x)+(v[k].y-v[j].y)*(v[k].y-v[j].y));
    double s3=sqrt((v[i].x-v[k].x)*(v[i].x-v[k].x)+(v[i].y-v[k].y)*(v[i].y-v[k].y));
    if(fabs(s1-s2-s3)<=EPS)
        return false;
    return true;
}
queue<int> q;
//SPFA最大费用最大流
bool EK(){
    q.push(S);
    for(int i=0;i<=n*2+1;i++)
        cost[i]=-INF;
    int w;
    cost[S]=0; flow[S]=INF; state[S]=1;
    while(!q.empty()){
        w=q.front(); q.pop(); state[w]=0;
        for(node *t=graph[w].pre;t;t=t->next){
            if(t->flow&&cost[t->to]<cost[w]+t->cost){
                cost[t->to]=cost[w]+t->cost;
                flow[t->to]=min(flow[w], t->flow);
                from[t->to]=t;
                if(!state[t->to]){
                    q.push(t->to);
                    state[t->to]=1;
                }
            }
        }
    }
    if(cost[T]==-INF) return false;
    ans+=cost[T];
    for(node *t=from[T];t;t=from[t->rev->to]){
        t->flow-=flow[T]; t->rev->flow+=flow[T];
    }
    return true;
}
//处理字符串
void fix(string &s){
    for(string::iterator it=s.begin();it!=s.end();it++)
        if(*it>='a')
            *it=*it-'a'+'A';
}
int main(){
    scanf("%d", &k); scanf("%d", &n);
    string s, en("End");
    for(int i=0;i<n*2;i++){
        cin>>v[i].x>>v[i].y>>s;
        fix(s);
        m.insert(make_pair(s, i));
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            karma[i][j+n]=1;
    map<string, int>::iterator it;
    cin>>s;
    int kar;
    while(s!=en){
        fix(s);
        it=m.find(s);
        int i=it->second;
        cin>>s>>kar;
        fix(s);
        it=m.find(s);
        int j=it->second;
        if(i>j)
            swap(i, j);
        karma[i][j]=kar;
        cin>>s;
    }
    //建图
    for(int i=0;i<n;i++){
        graph[S].push(i, 0, 1);
        graph[i].push(S, 0, 0);
        graph[S].last->rev=graph[i].last;
        graph[i].last->rev=graph[S].last;
        for(int j=n;j<n*2;j++){
            double s1=sqrt((v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y));
            if(s1>k) continue;
            bool f=1;
            for(int k=0;k<n*2;k++){
                if(i==k||j==k) continue;
                if(!check(s1, i, j, k)){
                    f=0;
                    break;
                }
            }
            if(f){
                graph[i].push(j, karma[i][j], 1);
                graph[j].push(i, -karma[i][j], 0);
                graph[i].last->rev=graph[j].last;
                graph[j].last->rev=graph[i].last;
            }
        }
        graph[i+n].push(T, 0, 1);
        graph[T].push(i+n, 0, 0);
        graph[T].last->rev=graph[i+n].last;
        graph[i+n].last->rev=graph[T].last;
    }
    //EK
    while(EK());
    printf("%d\n", ans);
    return 0;
}