题解 - Vijos

1

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int s_l=20,n_p_r=1,oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
vector<int> l;
vector<int> l_a;
vector<int> l_b;
vector<int> a_x;
vector<int> a_y;
vector<int> b_x;
vector<int> b_y;
vector<vector<int> > a_b_r;
vector<bool> v_a;
vector<bool> v_b;
vector<string> a_s;
vector<string> b_s;

bool check_1(int a,int b)
{
    if (pow(double(a_x[a]-b_x[b]),double(2))+pow(double(a_y[a]-b_y[b]),double(2))>pow(double(m),double(2)))
        return 0;
    for (int i=1;i<=n;i++)
        if (((a_x[a]<=a_x[i]&&a_x[i]<=b_x[b])||(b_x[b]<=a_x[i]&&a_x[i]<=a_x[a]))&&((a_y[a]<=a_y[i]&&a_y[i]<=b_y[b])||(b_y[b]<=a_y[i]&&a_y[i]<=a_y[a]))&&i!=a)
        {
            int a_i_x=a_x[i]-a_x[a],a_i_y=a_y[i]-a_y[a],i_b_x=b_x[b]-a_x[i],i_b_y=b_y[b]-a_y[i];
            if (a_i_x*i_b_y-i_b_x*a_i_y==0)
                return 0;
        }
    for (int i=1;i<=n;i++)
        if (((a_x[a]<=b_x[i]&&b_x[i]<=b_x[b])||(b_x[b]<=b_x[i]&&b_x[i]<=a_x[a]))&&((a_y[a]<=b_y[i]&&b_y[i]<=b_y[b])||(b_y[b]<=b_y[i]&&b_y[i]<=a_y[a]))&&i!=b)
        {
            int a_i_x=b_x[i]-a_x[a],a_i_y=b_y[i]-a_y[a],i_b_x=b_x[b]-b_x[i],i_b_y=b_y[b]-b_y[i];
            if (a_i_x*i_b_y-i_b_x*a_i_y==0)
                return 0;
        }
    return 1;
}

bool find_1(int now)
{
    v_a[now]=1;
    for (int i=1;i<=n;i++)
        if (v_b[i]==0&&l_a[now]+l_b[i]==a_b_r[now][i])
        {
            int temp=l[i];
            l[i]=now,v_b[i]=1;
            if (temp>0)
            {
                if (find_1(temp)==1)
                    return 1;
            }
            else
                return 1;
            l[i]=temp;
        }
    return 0;
}

int work_1()
{
    l.resize(0);
    l.resize(n+1,0);
    l_a.resize(0);
    l_a.resize(n+1,0);
    l_b.resize(0);
    l_b.resize(n+1,0);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            l_a[i]=max(l_a[i],a_b_r[i][j]);
    for (int now=1;now<=n;now++)
        while (1)
        {
            v_a.resize(0);
            v_a.resize(n+1,0);
            v_b.resize(0);
            v_b.resize(n+1,0);
            if (find_1(now)==1)
                break;
            int d=(numeric_limits<int>::max)();
            for (int i=1;i<=n;i++)
                if (v_a[i]==1)
                    for (int j=1;j<=n;j++)
                        if (v_b[j]==0)
                            d=min(d,l_a[i]+l_b[j]-a_b_r[i][j]);
            for (int i=1;i<=n;i++)
                l_a[i]-=((v_a[i]==1)?d:0);
            for (int i=1;i<=n;i++)
                l_b[i]+=((v_b[i]==1)?d:0);
        }
    int ans=0;
    for (int i=1;i<=n;i++)
        ans+=a_b_r[l[i]][i];
    return ans;
}

int main()
{
    while (~scanf("%d%d",&m,&n))
    {
        a_x.resize(0);
        a_x.resize(n+1,0);
        a_y.resize(0);
        a_y.resize(n+1,0);
        a_s.resize(0);
        a_s.resize(n+1);
        for (int i=1;i<=n;i++)
        {
            a_s[i].resize(0);
            a_s[i].resize(s_l,0);
            scanf("%d%d%s",&a_x[i],&a_y[i],&(a_s[i][0]));
            for (int j=0;j<a_s[i].size();j++)
                if ('A'<=a_s[i][j]&&a_s[i][j]<='Z')
                    a_s[i][j]+='a'-'A';
        }
        b_x.resize(0);
        b_x.resize(n+1,0);
        b_y.resize(0);
        b_y.resize(n+1,0);
        b_s.resize(0);
        b_s.resize(n+1);
        for (int i=1;i<=n;i++)
        {
            b_s[i].resize(0);
            b_s[i].resize(s_l,0);
            scanf("%d%d%s",&b_x[i],&b_y[i],&(b_s[i][0]));
            for (int j=0;j<b_s[i].size();j++)
                if ('A'<=b_s[i][j]&&b_s[i][j]<='Z')
                    b_s[i][j]+='a'-'A';
        }
        a_b_r.resize(0);
        a_b_r.resize(n+1);
        for (int i=1;i<=n;i++)
            a_b_r[i].resize(n+1,n_p_r);
        int p;
        string p_1_s,p_2_s,s_end="end";
        p_1_s.resize(0);
        p_1_s.resize(s_l,0);
        p_2_s.resize(0);
        p_2_s.resize(s_l,0);
        s_end.resize(s_l,0);
        while (~scanf("%s",&(p_1_s[0])))
        {
            for (int i=0;i<p_1_s.size();i++)
                if ('A'<=p_1_s[i]&&p_1_s[i]<='Z')
                    p_1_s[i]+='a'-'A';
            if (p_1_s!=s_end)
            {
                scanf("%s%d",&(p_2_s[0]),&p);
                for (int i=0;i<p_2_s.size();i++)
                    if ('A'<=p_2_s[i]&&p_2_s[i]<='Z')
                        p_2_s[i]+='a'-'A';
                bool b=0;
                for (int i=1;i<=n&&b==0;i++)
                    if (a_s[i]==p_1_s||a_s[i]==p_2_s)
                        for (int j=1;j<=n&&b==0;j++)
                            if ((a_s[i]==p_1_s&&b_s[j]==p_2_s)||(a_s[i]==p_2_s&&b_s[j]==p_1_s))
                                a_b_r[i][j]=p,b=1;
                p_1_s.resize(0);
                p_1_s.resize(s_l,0);
                p_2_s.resize(0);
                p_2_s.resize(s_l,0);
            }
            else
                break;
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (check_1(i,j)==0)
                    a_b_r[i][j]=oo_min;//不应该是0吗?
        printf("%d\n",work_1());
    }
}

sky1231 @ 7 年前

那个不应该是0吗？但是0会错第5个点

1

PowderHan LV 10 @ 7 年前

/*
二分图最优完美匹配       KM算法Orz
考虑到也就只有男的和女的两种人咯(难道还有双性？)
然后就很明显考虑到二分图咯   但是关键难点在于建图QAQ
QWQ而且字符串处理也很麻烦(对于我这种弱弱来说233333)
但主要是判断两个人是否能连成一条边啊
要满足两个条件
1.要在射程范围内，这个就很简单，我们直接求出两个点的欧几里德距离就好了
没啥很大的难度
2.两个人的连线上不能有另外一个人
这个也不麻烦，因为n也就不超过30吧，直接暴力一点咯
枚举所有人判断是否在一条直线上
如果三个点在一条直线上，那么一定可以根据直角三角形之类的组成相似三角形咯
这个就自行脑补了我提供了一种判断的方法
那么理清了这个我们在处理好name后，然后对于每对点，如果满足这个我们就拉一条无向边
这样就成功地构成了一个二分图模型QAQ
然后就是求这个二分图的最优完美匹配了
嗯这个就是裸的KM算法了(原谅我不会网络流啊)
然后我用的是O(n^4)的KM算法啊
实际上是可以优化顶标查找使算法到O(n^3)
Orz但是实际上这种图的最优匹配都是很好找的
所以O(n^4)比O(n^3)也慢不了多少
而且n也很小
所以偷个懒就写了个朴素的KM算法咯
也算是练习了一下KM算法了
一道好题~   调了一中午QAQ
还要特别注意的一个地方 对于两者不能连线的情况
一定要将其权值设为-INF而不能是0
不然第五个点稳稳地爆炸啊
QAQ一定要小心细节  一个地方炸了全都炸
建议每写好一个部分就测试一下  确保无误再写下一部分
但还是有个小小的疑惑在心里
在处理边的时候 本来按道理是男的和女的才能连边？
但是我直接男的和男的连边(标记的地方 把i,j的循环是对于所有n个点的)
结果也能AC  
这不符合我的意志    这非常尴尬QAQ
留到以后来考虑吧    先去QAQ了
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=2000;
const int INF=0x7fffff;
struct node
{
    int x,y;
}a[MAXN];
int n,m,maxd;
int w[MAXN][MAXN];
int lx[MAXN],ly[MAXN],slack[MAXN];
int s[MAXN],t[MAXN];
int match[MAXN];
int ans;
string name[MAXN];

bool Dist(int n1,int n2)
{
    return sqrt((a[n1].x-a[n2].x)*(a[n1].x-a[n2].x)
               +(a[n1].y-a[n2].y)*(a[n1].y-a[n2].y))<=maxd;
}

bool Dir(int n1,int n2)
{
    if(a[n1].x==a[n2].x)
    {
        for(int i=1;i<=n;i++)
            if(i!=n1&&i!=n2)
                if(a[i].x==a[n1].x)
                    if(a[i].y<=max(a[n1].y,a[n2].y))
                        if(a[i].y>=min(a[n1].y,a[n2].y))
                            return  false;
        return true;
    }
    else
    {
        for(int i=1;i<=n;i++)
                if(i!=n1&&i!=n2)
                    if(a[i].x<=max(a[n1].x,a[n2].x))
                        if(a[i].x>=min(a[n1].x,a[n2].x))
                            if((a[n1].y-a[i].y)*(a[n2].x-a[i].x)==
                               (a[n2].y-a[i].y)*(a[n1].x-a[i].x))
                                return false;
            return true;
    }
}

string change(string x)
{
    int k=x.length();
    for(int i=0;i<k;i++)
        if(x[i]>='A'&&x[i]<='Z')
            x[i]-=('A'-'a');
    return x;
}

void init()
{
    cin>>maxd>>n;
    n*=2;
    //for(int i=1;i<=n;i++)
        //for(int j=1;j<=n;j++)
            //w[i][j]=-INF;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y>>name[i];
    for(int i=1;i<=n;i++)
        name[i]=change(name[i]);
    string s1,s2;
    while(true)
    {
        cin>>s1;
        if(s1=="End")
            break;
        cin>>s2;
        s1=change(s1);
        s2=change(s2);
        int n1=0,n2=0;
        for(int i=1;i<=n;i++)
            if(name[i]==s1)
            {
                n1=i;
                break;
            }
        for(int i=1;i<=n;i++)
            if(name[i]==s2)
            {
                n2=i;
                break;
            }
        int k;
        cin>>k;
        if(Dist(n1,n2)&&Dir(n1,n2))
            w[n1][n2]=w[n2][n1]=k;
    }

    for(int i=1;i<=n/2;i++)
        for(int j=n/2;j<=n;j++)//Orz不解
            if(i!=j&&!w[i][j])
                if(Dist(i,j)&&Dir(i,j))
                    w[i][j]=w[j][i]=1;
    //没有边相连就要设为-INF而不能为0！！！
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!w[i][j])
                w[i][j]=-INF;
}

bool dfs(int x)
{
    s[x]=1;
    for(int i=1;i<=n;i++)
    {
        if(lx[x]+ly[i]==w[x][i]&&!t[i])
        {
            t[i]=1;
            if(!match[i]||dfs(match[i]))
            {
                match[i]=x;
                return true;
             }
        }
    }
    return false;
}

void update()
{
    int a=INF;
    for(int i=1;i<=n;i++)   if(s[i])
        for(int j=1;j<=n;j++)   if(!t[j])
            a=min(a,lx[i]+ly[j]-w[i][j]);
    for(int i=1;i<=n;i++)
    {
        if(s[i])    lx[i]-=a;
        if(t[i])    ly[i]+=a;
    }
}

void KM()
{
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            lx[i]=max(lx[i],w[i][j]);
    for(int i=1;i<=n;i++)
        for(;;)
        {
            memset(s,0,sizeof(s));
            memset(t,0,sizeof(t));
            if(dfs(i))
                break;
            else
                update();
        }
    for(int i=1;i<=n;i++)
        ans+=w[i][match[i]];
    cout<<ans/2<<endl;
}

int main()
{
    init();
    KM();
    return 0;
}

1

Bill_Yang LV 10 @ 8 年前

接楼下，再注意一点。
读入的坐标可能是实数！！！

1

叶德铭 LV 9 @ 15 年前

楼下大牛错的我都错了

要注意的几点

1.弓箭的射程有限。

2.箭的轨迹只能是一条直线，两个人之间的连线段不能有别人。

3.忽略大小写的区别。

4.如果没有被描述，则说明他们缘分值为1。

5.没提到的（可达的（注意两点）），缘分为1

6.重边取最后一条

7.第五个(完全匹配，费用流终结条件是找不到增广路，不是增广出

0

scjyholy LV 7 @ 8 年前

楼上这么多说数据有问题需要cheat、“数据剪枝”的，实际上只有第5个点有毒，**需要注意的是，如果两个人不连通边不能放进图！不只是边权为0！**

测试数据 #0: Accepted, time = 15 ms, mem = 580 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 584 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 584 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 584 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 584 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 584 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 584 KiB, score = 10
Accepted, time = 45 ms, mem = 584 KiB, score = 100

0

神犇 LV 10 @ 12 年前

感觉考点在字符串处理啊。。

6死活过不去cheat~

0

suifen123456 LV 8 @ 15 年前

要注意的几点

1.弓箭的射程有限。

2.箭的轨迹只能是一条直线，两个人之间的连线段不能有别人。

3.忽略大小写的区别。

4.如果没有被描述，则说明他们缘分值为1。

5.不用完全匹配。

至于重边....是不是数据有问题...

交了N次...T_T

0

Matt LV 10 @ 15 年前

一直在想PKU为什么过不了...

0

wll969 LV 8 @ 15 年前

我的天啊,"忽略大小写的区别"!!!!!!!!!!!

就因为这句没看到,浪费了我4个小时!!!

太惨了!!!!!!!!

0

TLD LV 10 @ 15 年前

用了一个简化版的费用流

0

唐钰小宝 LV 10 @ 15 年前

KM算法

0

我是姜逸伦大神 LV 8 @ 15 年前

水题。

费用流0MS，KM就不知道了

0

Hakkinen LV 8 @ 15 年前

注意点：

1.没有提及但满足条件的边边权为1

2.数据有重边情况，边权取最后一次出现的

0

cnnblike LV 9 @ 15 年前

底下的都是禽兽（即牛）……惨无人道地围观他们……某个善良的小孩飘过……

话说这道题目是用费用流还是KM?

我写的是KM算法……在T哥的指导下……

发现构图错误……汗……KM倒是没错很多……

最后cheat6、10两点

0

sxpeter LV 8 @ 15 年前

...

做了两天，一直卡在No.5上

最后看题解，发现**第5个点居然是错的！！！**

附：No.5 data,请管理员仔细检查

Input:

36

10

2 -7 aa

-23 -22 ab

-5 -16 ac

9 14 ad

8 -13 ae

3 7 af

-9 9 ag

8 22 ah

-9 -22 ai

14 13 aj

18 1 ba

2 23 bb

-14 0 bc

-24 -19 bd

18 -12 be

19 5 bf

-20 -17 bg

18 -19 bh

20 -3 bi

1 -16 bj

AC BG 90

AH BA 40

AE BE 89

BF AB 153

BG AD 188

AJ BF 109

AI BG 172

AG BH 161

AF BD 142

BD AC 239

AC BB 24

AH BD 201

BD AE 171

AJ BH 149

BF AH 6

BE AE 75

AJ BD 56

AA BJ 85

AE BA 251

AJ BJ 200

BE AC 74

AA BI 231

AF BB 79

AF BI 251

AI BB 160

BH AJ 118

BJ AA 208

AA BC 105

BF AC 75

BA AB 76

AJ BA 127

AA BI 16

BG AD 98

AD BI 134

BE AC 56

AF BH 21

BE AI 179

BH AG 192

AE BH 99

AC BJ 122

AF BB 112

BE AD 202

BD AJ 168

AB BF 199

AC BE 223

BE AI 85

AG BF 154

AI BG 191

AF BG 13

AF BI 160

BB AC 106

AH BH 16

AH BF 123

BJ AD 47

BJ AG 150

BI AC 250

BB AB 209

AE BI 116

BE AG 154

AC BH 18

AE BH 139

AG BC 134

AA BA 159

BC AC 217

AB BG 170

AA BB 202

End

Output:

1682

答案应该是1702

0

ipip2005 LV 10 @ 15 年前

KM算法有很多版本，我看的第一个版本浪费了我18小时，最后还是要无奈的cheat 5 10两点，就是用最小点覆盖的版本。现在用了新的版本，只要cheat第5个就能过了,oh yeah.费用流就不用cheat了，因为第5个数据就是用KM过不了，若有过了过了的大牛指教一下。~~~ls的数据，如果把不能连的边设为权值0就用KM过了，而标程估计是用费用流写的，把不能连的边删了，所以在满足最大流的前提下，最大费用就是2。错了.

有一个方法可以更正，把不能连的边赋值成-maxlongint而不是0

0

lijian3256 LV 10 @ 15 年前

没用网上流传的KM算法。对着算法导论敲。。。第十点无尽WA 比答案多6 额。。我太弱了只好CHeat 抚慰下。。

关于第五个点的解释：最优解不一定在最大匹配的时候形如

100 1

1 0

最大匹配情况下为2 而最优解为100

0

boyzkk LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

还是费用流实惠。注意大小写忽略。

0

czz5242199 LV 9 @ 15 年前

第100个AC，一个裸的KM算法

Flag 　　 Accepted

题号　　P1169

类型(?) 　　其它

通过　　100人

提交　　480次

通过率　　21%

难度　　4

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

voyagec2 LV 10 @ 16 年前

二分图最优匹配

KM太繁

转化成最大费用最大流

就是预处理恶心了

第5个点就是WA

无奈Cheat了

悲剧.

题解

41 条题解

丘比特的烦恼

信息

状态

开发

支持

题解

41 条题解

丘比特的烦恼

信息

状态

开发

支持

还没有账户？

登录