41 条题解

  • 1
    @ 2017-06-22 18:55:41
    #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());
        }
    }
    
    • @ 2017-06-22 18:57:48

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

  • 1
    @ 2017-05-08 12:32:58
    /*
    二分图最优完美匹配       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
    @ 2017-03-17 20:51:00

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

  • 1
    @ 2010-04-06 20:07:19

    楼下大牛错的我都错了

    要注意的几点

    1.弓箭的射程有限。

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

    3.忽略大小写的区别。

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

    5.没提到的(可达的(注意两点)) ,缘分为1

    6.重边取最后一条

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

  • 0
    @ 2016-08-14 08:30:22

    楼上这么多说数据有问题需要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
    @ 2012-08-13 20:47:34

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

    6死活过不去cheat~

  • 0
    @ 2009-11-10 16:46:22

    要注意的几点

    1.弓箭的射程有限。

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

    3.忽略大小写的区别。

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

    5.不用完全匹配。

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

    交了N次...T_T

  • 0
    @ 2009-10-25 01:02:57

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

  • 0
    @ 2009-10-03 20:00:52

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

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

    太惨了!!!!!!!!

  • 0
    @ 2009-08-12 12:26:19

    用了一个简化版的费用流

  • 0
    @ 2009-08-03 14:52:59

    KM算法

  • 0
    @ 2009-07-28 13:40:56

    水题。

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

  • 0
    @ 2009-07-28 13:34:45

    注意点:

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

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

  • 0
    @ 2009-07-26 20:45:03

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

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

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

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

    最后cheat6、10两点

  • 0
    @ 2009-07-24 16:01:42

    ...

    做了两天,一直卡在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
    @ 2009-07-21 16:31:44

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

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

  • 0
    @ 2009-07-21 11:31:19

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

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

    100 1

    1 0

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

  • 0
    @ 2009-07-20 09:52:05

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-04-29 22:26:23

    第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
    @ 2009-04-17 15:37:14

    二分图最优匹配

    KM太繁

    转化成最大费用最大流

    就是预处理恶心了

    第5个点就是WA

    无奈Cheat了

    悲剧.

信息

ID
1169
难度
7
分类
图结构 | 二分图 点击显示
标签
递交数
717
已通过
149
通过率
21%
被复制
4
上传者