线性规划与网络流24题魔术球

题目描述 Description

    假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1，2，3，…的球。
    （1）每次只能在某根柱子的最上面放球。
    （2）在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。
    试设计一个算法，计算出在 n 根柱子上最多能放多少个球。例如，在 4 根柱子上最多可放 11 个球。
    对于给定的 n，计算在 n 根柱子上最多能放多少个球。

输入描述 Input Description

    第 1 行有 1 个正整数 n，表示柱子数。

输出描述 Output Description

    将 n 根柱子上最多能放的球数以及相应的放置方案输出

    第一行是球数。接下来的 n 行，每行是一根柱子上的球的编号。

样例输入 Sample Input

    4

样例输出 Sample Output

    11

    1 8 

    2 7 9 

    3 6 10 

    4 5 11

就不多说了，如果i<j,i+j是一个完全平方数,就从i向j连一条边

然后求最小路径覆盖，所以可以转化成二分图最大匹配，所以又可以转化成网络流

本来是想用二分图匹配的匈牙利来做，但是每一次都要重新构图，所以还是用网络流了

后来想到匈牙利只要加一个条件就行了，只要x没有匹配就可以从这里增广，每一次都只是加边就行了，比网络流快了很多（不过多种方案，答案跟标准答案不一样，网络流是把一个地方改成downto才对的，二分图就没办法了，不过还是贴一下吧）

 1 const
 2     maxn=1600;
 3     maxm=1000000;
 4 var
 5     n,k,i,p,tot,time:longint;
 6     first,next,last:array[0..maxm]of longint;
 7     flagx:array[0..maxn]of boolean;
 8     flag,link,nextball:array[0..maxn]of longint;
 9 
10 procedure insert(x,y:longint);
11 begin
12     inc(tot);
13     last[tot]:=y;
14     next[tot]:=first[x];
15     first[x]:=tot;
16 end;
17 
18 function path(x:longint):boolean;
19 var
20     i:longint;
21 begin
22     i:=first[x];
23     while i<>0 do
24       begin
25         if last[i]<=n then
26         if flag[last[i]]<>time then
27         begin
28           flag[last[i]]:=time;
29           if (link[last[i]]=0)or(path(link[last[i]])) then
30           begin
31             link[last[i]]:=x;
32             flagx[x]:=true;
33             exit(true);
34           end;
35         end;
36         i:=next[i];
37       end;
38     exit(false);
39 end;
40 
41 procedure work;
42 var
43     i:longint;
44 begin
45     for i:=1 to n-1 do
46       if flagx[i]=false then
47       begin
48         inc(time);
49         if path(i) then inc(p);
50       end;
51 end;
52 
53 procedure print;
54 var
55     i,j:longint;
56 begin
57     for i:=1 to n do
58       nextball[link[i]]:=i;
59     inc(time);
60     for i:=1 to n do
61       if flag[i]<>time then
62       begin
63         j:=i;
64         while j<>0 do
65           begin
66             flag[j]:=time;
67             write(j,' ');
68             j:=nextball[j];
69           end;
70         writeln;
71       end;
72 end;
73 
74 begin
75     read(k);
76     while n-p<=k do
77       begin
78         inc(n);
79         for i:=1 to n-1 do
80           if sqr(trunc(sqrt(i+n)))=i+n then insert(i,n);
81         work;
82       end;
83     dec(n);
84     writeln(n);
85     for i:=1 to n do
86       flagx[i]:=false;
87     for i:=1 to n do
88       link[i]:=0;
89     work;
90     print;
91 end.

二分图匈牙利

  1 const
  2     maxn=3200;
  3 var
  4     map,a:array[0..maxn,0..maxn]of longint;
  5     dis,vh,his,pre,next:array[0..maxn]of longint;
  6     f:array[0..maxn]of boolean;
  7     k,n,p,i,j,aug:longint;
  8     flag:boolean;
  9 
 10 procedure work;
 11 var
 12     i,j,k,min:longint;
 13 begin
 14     for i:=1 to n do
 15       begin
 16         dis[i]:=0;
 17         dis[i+1600]:=0;
 18       end;
 19     dis[0]:=0;
 20     dis[3200]:=0;
 21     for i:=1 to 2*n+2 do
 22       vh[i]:=0;
 23     vh[0]:=2*n+2;
 24     aug:=maxlongint;
 25     i:=0;
 26     while dis[0]<2*n+2 do
 27       begin
 28         his[i]:=aug;
 29         flag:=false;
 30         for j:=a[i,0] downto 1 do
 31           if (map[i,a[i,j]]>0)and(dis[i]=dis[a[i,j]]+1) then
 32           begin
 33             flag:=true;
 34             pre[a[i,j]]:=i;
 35             if aug>map[i,a[i,j]] then aug:=map[i,a[i,j]];
 36             i:=a[i,j];
 37             if i=3200 then
 38             begin
 39               inc(p,aug);
 40               while i<>0 do
 41                 begin
 42                   k:=pre[i];
 43                   dec(map[k,i],aug);
 44                   inc(map[i,k],aug);
 45                   i:=k;
 46                 end;
 47               aug:=maxlongint;
 48             end;
 49             break;
 50           end;
 51         if flag then continue;
 52         min:=2*n+1;
 53         for j:=1 to a[i,0] do
 54           if (map[i,a[i,j]]>0)and(dis[a[i,j]]<min) then min:=dis[a[i,j]];
 55         dec(vh[dis[i]]);
 56         if vh[dis[i]]=0 then break;
 57         dis[i]:=min+1;
 58         inc(vh[dis[i]]);
 59         if i<>0 then
 60         begin
 61           i:=pre[i];
 62           aug:=his[i];
 63         end;
 64       end;
 65 end;
 66 
 67 procedure print;
 68 var
 69     i,j:longint;
 70 begin
 71     for i:=1 to n do
 72       for j:=1 to a[i,0] do
 73         if map[i,a[i,j]]=0 then next[i]:=a[i,j]-1600;
 74     for i:=1 to n do
 75       if f[i]=false then
 76       begin
 77         j:=i;
 78         while j<>0 do
 79           begin
 80             f[j]:=true;
 81             write(j,' ');
 82             j:=next[j];
 83           end;
 84         writeln;
 85       end;
 86 end;
 87 
 88 begin
 89     read(k);
 90     n:=0;
 91     while n-p<=k do
 92       begin
 93           inc(n);
 94         inc(a[0,0]);
 95         a[0,a[0,0]]:=n;
 96         inc(map[0,n]);
 97         inc(a[n+1600,0]);
 98         a[n+1600,a[n+1600,0]]:=3200;
 99         inc(map[n+1600,3200]);
100         for i:=1 to n-1 do
101           if sqr(trunc(sqrt(i+n)))=i+n then
102           begin
103             inc(map[i,n+1600]);
104             inc(a[i,0]);
105             a[i,a[i,0]]:=n+1600;
106             inc(a[n+1600,0]);
107             a[n+1600,a[n+1600,0]]:=i;
108           end;
109         work;
110       end;
111     dec(n);
112     fillchar(map,sizeof(map),0);
113     dec(a[0,0]);
114     for i:=1 to n do
115       begin
116         map[0,i]:=1;
117         map[i+1600,3200]:=1;
118         if a[i,a[i,0]]=n+1+1600 then dec(a[i,0]);
119         for j:=1 to a[i,0] do
120           map[i,a[i,j]]:=1;
121       end;
122     work;
123     writeln(n);
124     print;
125 end.

网络流sap

线性规划与网络流24题 魔术球

线性规划与网络流24题魔术球