7
31
2013
1

【BZOJ2539】【Ctsc2000】丘比特的烦恼【KM】

很裸的KM算法，但是数据极其恶心。调了我好几个月才A掉（一开始在VIJOS做，然后跳过，今天重新开始做），要注意的是后面输入的缘分值可能为0，所以要把不能射箭两个人之间连上-maxlongint的边，不能连0。还有就是坐标可能不是整数，应当用浮点型存储。

 

?
BZOJ2539
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
program p2539;
    type
        people=record
            na:string;
            xx,yy:extended;
        end;
    var
        x,y,aimy:array[1..100] of longint;
        vx,vy:array[1..100] of boolean;
        w:array[1..100,1..100] of longint;
        p:array[1..200] of people;
        n,m,i,j,k,a,b,c:longint;
        d:extended;
        ss,s:string;
    function max(k1,k2:extended):extended;
        begin
            if k1<k2 then exit(k2) else exit(k1);
        end;
    function min(k1,k2:extended):extended;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    function find(k:longint):boolean;
        var
            i,j,kk:longint;
        begin
            if k=0 then exit(false);
            vx[k]:=true;
            for i:=1 to n do
                if (vy[i]=false) and (x[k]+y[i]=w[k,i]) then begin
                    vy[i]:=true;
                    if (aimy[i]=0) or (find(aimy[i])) then begin
                        aimy[i]:=k;
                        exit(true);
                    end;
                end;
            exit(false);
        end;
    begin
        readln(d);
        readln(n);
        for i:=1 to 2*n do begin
            readln(s);
            j:=1;
            while (s[j+1]<>' ') do
                inc(j);
            val(copy(s,1,j),p[i].xx,a);
            j:=j+2;
            k:=1;
            while (s[j+k]<>' ') do
                inc(k);
            val(copy(s,j,k),p[i].yy,a);
            p[i].na:=copy(s,j+k+1,length(s)-j-k);
            for j:=1 to length(p[i].na) do
                p[i].na[j]:=upcase(p[i].na[j]);
        end;
        readln(s);
        for i:=1 to n do
            for j:=1 to n do
                w[i,j]:=1;
        while s<>'End' do begin
            i:=1;
            k:=1;
            while s[i+k]<>' ' do
                inc(k);
            ss:=copy(s,i,k);
            for j:=1 to length(ss) do
                ss[j]:=upcase(ss[j]);
            for a:=1 to 2*n do
                if ss=p[a].na then break;
            i:=i+k+1;
            k:=1;
            while s[i+k]<>' ' do
                inc(k);
            ss:=copy(s,i,k);
            for j:=1 to length(ss) do
                ss[j]:=upcase(ss[j]);
            for b:=1 to 2*n do
                if ss=p[b].na then break;
            val(copy(s,i+k+1,length(s)-i-k),c,j);
            if a>b then w[b,a-n]:=c
                else w[a,b-n]:=c;
            readln(s);
        end;
        for i:=1 to n do
            for j:=1 to n do begin
                if sqr(p[i].xx-p[j+n].xx)+sqr(p[i].yy-p[j+n].yy)>sqr(d) then begin
                    w[i,j]:=-1000000000;
                    continue;
                end;
                for k:=1 to n*2 do
                    if (k<>i) and (k<>j+n) and ((p[i].xx-p[j+n].xx)*(p[i].yy-p[k].yy)=(p[i].yy-p[j+n].yy)*(p[i].xx-p[k].xx))then begin
                        if (p[k].xx>max(p[i].xx,p[j+n].xx)) or (p[k].xx<min(p[i].xx,p[j+n].xx)) or (p[k].yy>max(p[i].yy,p[j+n].yy)) or (p[k].yy<min(p[i].yy,p[j+n].yy)) then
                            continue;
                        w[i,j]:=-1000000000;
                        break;
                    end;
            end;
        {for i:=1 to n do begin
            for j:=1 to n do
                write(w[i,j],' ');
            writeln;
        end;
}        fillchar(y,sizeof(y),0);
        fillchar(x,sizeof(x),0);
        for i:=1 to n do
            for j:=1 to n do
                x[i]:=trunc(max(x[i],w[i,j]));
        fillchar(aimy,sizeof(aimy),0);
        for k:=1 to n do
            repeat
                {for i:=1 to n do
                    write(aimy[i],' ');
                readln;}
                fillchar(vx,sizeof(vx),false);
                fillchar(vy,sizeof(vy),false);
                if find(k) then break;
                c:=1000000;
                for i:=1 to n do begin
                    if not vx[i] then continue;
                    for j:=1 to n do begin
                        if vy[j] then continue;
                        c:=trunc(min(c,x[i]+y[j]-w[i,j]));
                    end;
                end;
                for i:=1 to n do begin
                    if vx[i] then x[i]:=x[i]-c;
                    if vy[i] then y[i]:=y[i]+c;
                end;
            until false;
        a:=0;
        for i:=1 to n do
            a:=a+w[aimy[i],i];
        writeln(a);
        {for i:=1 to n do
            writeln(aimy[i],' ',w[aimy[i],i]);
        readln;
        readln;}
    end.
Category: KM | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com