AbOr's story --FOJ 1980
28585 ワード
1、テーマタイプ:図論、最大流、最小切断最大流定理、Dinicアルゴリズム.
2、問題を解く構想:「アルゴリズム芸術と情報学コンテスト」では説明の原題を変えただけだ(P 317).(1)二分図Gを構築し、そのX接点はすべての宝石であり、各宝石iはXiで表され、Ii容量のアークS-Yiを接続する.そのYノードはすべての女の子であり、各女の子iはYiで表され、Eiの容量を持つアークYi-Tを接続している.(2)最小切断最大流の定理(証明)、ステップ1:最小切断は無限容量のエッジを含むことができない.これは明らかであり、したがって、Tセットのいずれかの女の子Ejが宝石Ijを必要とする場合、IjもTセットにあり、切断が実行可能なスキームに対応することを保証する.ステップ2:いずれかの宝石iについて、宝石がTセットにある場合、その宝石が購入されるべきであることを示し、このとき容量Iiは切断中に計算される.いずれの女の子jについても、女の子が集合Tで女の子が選択されたことを示す場合、容量Ejは切断中に計算されず、このスキームに対応する切断数値はsum{Ii}+sum{Ej}に等しい.(3)すべての女の子の総収益Eであれば,最大収益=E−(sum{Ii}+sum{Ej})となる.
3、注意事项:最大ストリームの解に注意して、この问题はDinicアルゴリズムだけが题意に合って、Ford-Fulkersonアルゴリズム、SAPアルゴリズムTLE.
4、実現方法:
2、問題を解く構想:「アルゴリズム芸術と情報学コンテスト」では説明の原題を変えただけだ(P 317).(1)二分図Gを構築し、そのX接点はすべての宝石であり、各宝石iはXiで表され、Ii容量のアークS-Yiを接続する.そのYノードはすべての女の子であり、各女の子iはYiで表され、Eiの容量を持つアークYi-Tを接続している.(2)最小切断最大流の定理(証明)、ステップ1:最小切断は無限容量のエッジを含むことができない.これは明らかであり、したがって、Tセットのいずれかの女の子Ejが宝石Ijを必要とする場合、IjもTセットにあり、切断が実行可能なスキームに対応することを保証する.ステップ2:いずれかの宝石iについて、宝石がTセットにある場合、その宝石が購入されるべきであることを示し、このとき容量Iiは切断中に計算される.いずれの女の子jについても、女の子が集合Tで女の子が選択されたことを示す場合、容量Ejは切断中に計算されず、このスキームに対応する切断数値はsum{Ii}+sum{Ej}に等しい.(3)すべての女の子の総収益Eであれば,最大収益=E−(sum{Ii}+sum{Ej})となる.
3、注意事项:最大ストリームの解に注意して、この问题はDinicアルゴリズムだけが题意に合って、Ford-Fulkersonアルゴリズム、SAPアルゴリズムTLE.
4、実現方法:
#include
<
iostream
>
#define
MAXN 20010
#define
MAXM 200000
#define
INIFINITY 10000000000
using
namespace
std;
typedef __int64 FLOW;
struct
Edge {
//
v:adjacent to, r: remains, c: capacity
int
v;
FLOW r, c;
Edge
*
next;
//
adjacent list
Edge
*
Reverse();
//
get the pointer of reverse edge
};
struct
Vertex {
Edge
*
first;
//
first adjacent edge of the vertex
};
Edge edges[MAXM];
//
edges's list
Vertex g[MAXN];
//
vertexes's list
int
n, m, s, t;
//
vertex's number, edges's number, source, terminal
int
dest;
//
the vertex ending the dfs process
int
d[MAXN];
//
the level of the vertex(dinic); the distance to t (SAP)
//
get the reference of the reverse edge of it
Edge inline
*
Edge::Reverse()
{
return
edges
+
((
this
-
edges)
^
1
);
}
void
AddEdge(
int
u,
int
v, FLOW c)
{
//
add sigle edge to network
edges[m].v
=
v;
edges[m].r
=
c;
//
notation: use .r or use .c
edges[m].next
=
g[u].first;
g[u].first
=
edges
+
m;
m
++
;
}
void
Insert(
int
u,
int
v, FLOW c1, FLOW c2)
{
//
insert a two-way edge
AddEdge(u, v, c1);
AddEdge(v, u, c2);
}
//
bfs to construct the level graph
bool
BFS_Dinic(
int
s,
int
t,
int
n)
{
int
Q[MAXN];
//
queue to construct level graph
int
front, rear, u;
for
(u
=
0
; u
<
n; u
++
) d[u]
=
n;
front
=
rear
=
0
;
Q[rear
++
]
=
t;
d[t]
=
n
-
1
;
while
(front
<
rear)
{
u
=
Q[front
++
];
for
(Edge
*
p
=
g[u].first; p; p
=
p
->
next)
{
if
(p
->
Reverse()
->
r
>
0
&&
d[p
->
v]
==
n)
{
d[p
->
v]
=
d[u]
-
1
;
Q[rear
++
]
=
p
->
v;
if
(p
->
v
==
s)
return
true
;
}
}
//
for*/
}
//
while
return
false
;
}
//
sub function of Dinic_DFS
FLOW DFS_Dinic(Edge
*
e, FLOW flow)
{
FLOW f
=
0
;
if
(e
->
r
<
flow) flow
=
e
->
r;
if
(e
->
v
==
dest)
f
=
flow;
else
{
for
(Edge
*
p
=
g[e
->
v].first; p
&&
(f
<
flow); p
=
p
->
next)
{
//
f < flow is important
if
(p
->
r
>
0
&&
d[p
->
v]
>
d[e
->
v])
{
//
-> d[p->v] == d[e->v] + 1
f
+=
DFS_Dinic(p, flow
-
f);
}
}
}
e
->
r
-=
f;
e
->
Reverse()
->
r
+=
f;
return
f;
}
//
main function of dinic algorithm
FLOW Dinic(
int
s,
int
t,
int
n)
{
FLOW maxflow
=
0
;
Edge
*
first
=
edges
+
m
+
1
;
first
->
v
=
s;
dest
=
t;
while
(
true
) {
first
->
r
=
INIFINITY;
if
(
!
BFS_Dinic(s, t, n))
break
;
//
t not in residual network
maxflow
+=
DFS_Dinic(first, INIFINITY);
}
return
maxflow;
}
int
wm,bs;
FLOW sum;
void
Init()
{
int
i,j,b,c,cnt;
scanf(
"
%d%d
"
,
&
wm,
&
bs);
s
=
0
;m
=
0
;sum
=
0
;
t
=
wm
+
bs
+
1
;n
=
t
+
1
;
for
(i
=
0
;i
<
n;i
++
)
g[i].first
=
NULL;
for
(i
=
1
;i
<=
wm;i
++
)
{
scanf(
"
%d
"
,
&
cnt);
for
(j
=
0
;j
<
cnt;j
++
)
{
scanf(
"
%d
"
,
&
b);
Insert(b,i
+
bs,INIFINITY,
0
);
}
scanf(
"
%d
"
,
&
c);
sum
+=
c;
Insert(i
+
bs,t,c,
0
);
}
for
(j
=
1
;j
<=
bs;j
++
)
{
scanf(
"
%d
"
,
&
c);
Insert(s,j,c,
0
);
}
}
int
main()
{
int
T, ca
=
1
;
scanf(
"
%d
"
,
&
T);
while
(T
--
)
{
Init();
sum
-=
Dinic(s,t,n);
printf(
"
Case %d: %I64d
"
,ca
++
,sum);
}
return
0
;
}