10
16
2013
1

【BZOJ2007】【Noi2010】海拔【最小割+最短路】

语文挂科了，所以来除草了。

program p2007;

?
BZOJ2007
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
type
    d=record
        w,po:int64;
    end;
    bian=record
        next,point,w:int64;
    end;
var
    b:array[1..1000000] of bian;
    i,j,n,k1,k2,len:longint;
    x:array[1..1000000] of d;
    p,f:array[0..1000000] of int64;
    pd:array[0..1000000] of boolean;
    maxn:int64;
procedure add(k1,k2,k3:longint);
    begin
        inc(len);
        b[len].next:=p[k1];
        b[len].point:=k2;
        b[len].w:=k3;
        p[k1]:=len;
    end;
function mi(k1,k2:longint):longint;
    begin
        if x[k1].w>x[k2].w then exit(k2) else exit(k1);
    end;
function min(k1,k2,k3:longint):longint;
    begin
        exit(mi(mi(k1,k2),k3));
    end;
procedure press(k:longint);
    var
        k1:longint;
        k2:d;
    begin
        k1:=min(k,k*2,k*2+1);
        if k1=k then exit;
        k2:=x[k1];
        x[k1]:=x[k];
        x[k]:=k2;
        press(k1);
    end;
procedure find(k:longint);
    var
        k1:d;
    begin
        if k=1 then exit;
        if x[k div 2].w>x[k].w then begin
            k1:=x[k];
            x[k]:=x[k div 2];
            x[k div 2]:=k1;
            find(k div 2);
        end;
    end;
function dijstra:longint;
    var
        k1,k2,k3,i,j,now,len:longint;
        k:d;
    begin
        fillchar(pd,sizeof(pd),true);
        fillchar(x,sizeof(x),$7f);
        maxn:=x[1].po; len:=1;
        fillchar(f,sizeof(f),$3f);
        x[1].po:=0; x[1].w:=0; f[0]:=0;
        while len>0 do begin
            len:=len-1;
            k:=x[1];
            if len>0 then begin
                x[1]:=x[len+1];
                x[len+1].w:=maxn;
                press(1);
            end;
            if pd[k.po]=false then continue;
            pd[k.po]:=false;
            k2:=p[k.po];
            while k2>0 do begin
                k1:=b[k2].point;
                if f[k.po]+b[k2].w<f[k1] then begin
                    f[k1]:=f[k.po]+b[k2].w;
                    inc(len);
                    x[len].po:=k1; x[len].w:=f[k1];
                    find(len);
                end;
                k2:=b[k2].next;
            end;
        end;
        exit(f[n*n+1]);
    end;
begin
    fillchar(b,sizeof(b),0);
    fillchar(p,sizeof(p),0);
    len:=0;
    readln(n);
    for i:=1 to n+1 do
        for j:=1 to n do begin
            readln(k1);
            if i=1 then
                add(j,n*n+1,k1)
            else if i=n+1 then
                add(0,n*(n-1)+j,k1)
            else add(n*(i-1)+j,n*(i-2)+j,k1);
        end;
    for i:=1 to n do begin
        readln(k1);
        add(0,n*i-n+1,k1);
        for j:=1 to n-1 do begin
            readln(k1);
            add(n*i-n+j,n*i-n+j+1,k1);
        end;
        readln(k1);
        add(n*i,n*n+1,k1);
    end;
    for i:=1 to n+1 do
        for j:=1 to n do begin
            readln(k1);
            if (i<>1) and (i<>n+1) then add(n*(i-2)+j,n*(i-1)+j,k1);
        end;
    for i:=1 to n do begin
        readln(k1);
        for j:=1 to n-1 do begin
            readln(k1);
            add(n*i-n+j+1,n*i-n+j,k1);
        end;
        readln(k1);
    end;
    fillchar(x,sizeof(x),$3f);
    fillchar(f,sizeof(f),$3f);
    maxn:=x[1].po;
    writeln(dijstra);
end.

一眼就可以看出来是最小割，因为显而易见每个点的高度只可能是0或1，那么它们必有一个交接面，而这个就需要用最小割了。但是最小割会T80，所以要用对偶图+最短路来解决最小割问题，就如BZOJ1001。而这题恶心的把SPFA卡了，我又都比的把DJ+堆敲炸了，这道题就坑了我一个晚上QAQ（虽然有OSU和CS的因素）。

 

Category: 最短路 | Tags:
9
4
2013
0

【BZOJ1491】【NOI2007】社交网络【弗洛伊德】

两个弗洛伊德+乘法原理，第二个弗洛伊德居然写错了。。调了半天才调出来，QAQ

?
BZOJ1491
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
program p1491;
    var
        b,f:array[1..300,1..300] of int64;
        w:array[1..300] of extended;
        n,m,i,j,k1,k2,k3,k:longint;
    begin
        fillchar(f,sizeof(f),0);
        fillchar(b,sizeof(b),$3f);
        readln(n,m);
        for i:=1 to m do begin
            readln(k1,k2,k3);
            if k3<b[k1,k2] then begin
                b[k1,k2]:=k3;
                b[k2,k1]:=k3;
                f[k1,k2]:=1;
                f[k2,k1]:=1;
            end;
        end;
        for k:=1 to n do
            for i:=1 to n do
                for j:=1 to n do begin
                    if (i=j) or (j=k) or (k=i) then continue;
                    if b[i,k]+b[k,j]<b[i,j] then begin
                        b[i,j]:=b[i,k]+b[k,j];
                        f[i,j]:=f[i,k]*f[k,j];
                    end else if b[i,k]+b[k,j]=b[i,j] then
                        f[i,j]:=f[i,j]+f[i,k]*f[k,j];
                end;
        fillchar(w,sizeof(w),0);
        for k:=1 to n do
            for i:=1 to n do
                for j:=1 to n do
                    if (i<>k) and (j<>k) and (b[i,k]+b[k,j]=b[i,j])and (i<>j)then
                        w[k]:=w[k]+f[i,k]*f[k,j]/f[i,j];
        for i:=1 to n do
            writeln(w[i]:0:3);
    end.
Category: 最短路 | Tags:
7
30
2013
1

【BZOJ1001】【BeiJing2006】狼抓兔子【最小割+最短路】

这道题是一道很裸最小割，但是由于数据范围太大，所以要用最短路来实现。建图比较诡异，详情看代码。

?
BZOJ1001
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
program p1001;
    type
        bian=record
            point,next,w:longint;
        end;
        d=record
            po,w:longint;
        end;
    var
        p,f:array[0..3000000] of longint;
        b:array[1..9000000] of bian;
        x:array[1..3000000] of d;
        pd:array[0..2000000] of boolean;
        maxn,k1,k2,k3,n,m,i,j,len,t1,t2:longint;
    procedure ade(k1,k2,k3:longint);
        begin
            inc(len);
            b[len].w:=k3;
            b[len].point:=k2;
            b[len].next:=p[k1];
            p[k1]:=len;
        end;
    procedure charu(k1,k2,k3:longint);
        begin
            ade(k1,k2,k3);
            ade(k2,k1,k3);
        end;
    function mi(k1,k2:longint):longint;
        begin
            if x[k1].w>x[k2].w then exit(k2) else exit(k1);
        end;
    function min(k1,k2,k3:longint):longint;
        begin
            exit(mi(mi(k1,k2),k3));
        end;
    procedure press(k:longint);
        var
            k1:longint;
            k2:d;
        begin
            k1:=min(k,k*2,k*2+1);
            if k1=k then exit;
            k2:=x[k1];
            x[k1]:=x[k];
            x[k]:=k2;
            press(k1);
        end;
    procedure find(k:longint);
        var
            k1:d;
        begin
            if k=1 then exit;
            if x[k div 2].w>x[k].w then begin
                k1:=x[k];
                x[k]:=x[k div 2];
                x[k div 2]:=k1;
                find(k div 2);
            end;
        end;
    function dijstra:longint;
        var
            k1,k2,k3,i,j,now,len:longint;
            k:d;
        begin
            fillchar(pd,sizeof(pd),true);
            fillchar(x,sizeof(x),$7f);
            maxn:=x[1].po; len:=1;
            fillchar(f,sizeof(f),$3f);
            x[1].po:=0; x[1].w:=0; f[0]:=0;
            while len>0 do begin
                len:=len-1;
                k:=x[1];
                if len>0 then begin
                    x[1]:=x[len+1];
                    x[len+1].w:=maxn;
                    press(1);
                end;
                if pd[k.po]=false then continue;
                pd[k.po]:=false;
                k2:=p[k.po];
                while k2>0 do begin
                    k1:=b[k2].point;
                    if f[k.po]+b[k2].w<f[k1] then begin
                        f[k1]:=f[k.po]+b[k2].w;
                        inc(len);
                        x[len].po:=k1; x[len].w:=f[k1];
                        find(len);
                    end;
                    k2:=b[k2].next;
                end;
            end;
            exit(f[t2]);
        end;
    begin
        readln(n,m);
        len:=0;
        fillchar(p,sizeof(p),0);
        fillchar(b,sizeof(b),0);
        t1:=(n-1)*(m-1);
        t2:=t1*2+1;
        if (n=1) and (m=1) then begin
            writeln(0);
            exit;
        end;
        for i:=1 to n do
            for j:=1 to m-1 do begin
                read(k1);
                if i=1 then k2:=0 else k2:=(i-2)*(m-1)+j+t1;
                if i=n then k3:=t2 else k3:=(i-1)*(m-1)+j;
                charu(k2,k3,k1);
            end;
        for i:=1 to n-1 do
            for j:=1 to m do begin
                read(k1);
                if j=1 then k2:=t2 else k2:=(i-1)*(m-1)+j-1;
                if j=m then k3:=0 else k3:=(i-1)*(m-1)+j+t1;
                charu(k2,k3,k1);
            end;
        for i:=1 to n-1 do
            for j:=1 to m-1 do begin
                read(k1);
                k2:=(i-1)*(m-1)+j;
                k3:=(i-1)*(m-1)+j+t1;
                charu(k2,k3,k1);
            end;
        writeln(dijstra);
    end.
                
Category: 最短路 | Tags:

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