第七场春训，谢谢szh、zkj学长 qwq！ （补题式学习法）
【BUAA Spring Training 07】
Tags：最大流 费用流 可行流 二分图
Problem A. Petya and Graph
[A] 题意
一个子图是由原图边的子集和点的子集构成的图（每条边的端点必须是点子集中的点）
子图的权值总和定义为这个子图的边权和减去点权和。
给定一个没有自环重边的无向图，求最大子图权值。点数边数都
∈
[
1
,
1
0
3
]
\in [1, 10^3]
∈[1,103]
[A] 思路
看到这个范围就应该想到是网络流…
我们把每条边视为一个中介点，那么问题就转换为了典型的最大权闭合子图。
建图方式就是，原图每个结点以点权为容量连向超级汇，然后把每条边拆成一个中介点，从超级源拉一条容量为边权的弧过来，接着再把中介点和原边的两个端点以无穷容量连接就行了。
然后把原图边权全部相加，再减去建图后的最大流就是答案。
时间复杂度：网络流，你懂的，
O
(
O(
O(能过
)
)
)。
[A] 代码
#include
<cstdio
>
#include
<cstring
>
#include
<limits
>
#define
LL long long
#define
ULL unsigned
LL
#define _BS
1048576
char _bf
[_BS
];
char
*__p1
=_bf
,*__p2
=_bf
;
#define _IO char
*_p1
=__p1
,*_p2
=__p2
;
#define _OI __p1
=_p1
,__p2
=_p2
;
#ifdef _KEVIN
#define
GC getchar()
#
else
#define
GC (_p1
==_p2
&&(_p2
=(_p1
=_bf
)+fread(_bf
,1,_BS
,stdin
),_p1
==_p2
)?EOF:*_p1
++)
#endif
#define
PC putchar
#define
_Q_(x
) {register char _c
=GC,_v
=1;for(x
=0;_c
<48||_c
>57;_c
=GC)if(_c
==45)_v
=-1;
#define
_H_(x
) for(;_c
>=48&&_c
<=57;x
=(x
<<1)+(x
<<3)+_c
-48,_c
=GC);if(_v
==-1)x
=-x
;}
#define
sc(x
) _Q_(x
)_H_(x
)
#define
se(x
) _Q_(x
)else if(_c
==EOF)return 0;_H_(x
)
#define
_G1(_1
) int _1
;sc(_1
)
#define
_G2(_1
,_2
) int _1
,_2
;sc(_1
)sc(_2
)
#define
_G3(_1
,_2
,_3
) int _1
,_2
,_3
;sc(_1
)sc(_2
)sc(_3
)
#define
_gG(_1
,_2
,_3
,_get
, ...) _get
#define
get(...) _gG(__VA_ARGS__
,_G3
,_G2
,_G1
, ...)(__VA_ARGS__
)
#define
_F0N(i
,n
) for(auto i
=0;i
<(n
);++i
)
#define
_FLR(i
,l
,r
) for(auto i
=(l
);i
<(r
);++i
)
#define
_gF(_1
, _2
, _3
, _F
, ...) _F
#define
F(...) _gF(__VA_ARGS__
,_FLR
,_F0N
, ...)(__VA_ARGS__
)
#define
_FD0(i
,n
) for(auto i
=0;i
<=(n
);++i
)
#define
_FDL(i
,l
,r
) for(auto i
=(l
);i
<=(r
);++i
)
#define
_gFD(_1
, _2
, _3
, _FD
, ...) _FD
#define
FD(...) _gFD(__VA_ARGS__
,_FDL
,_FD0
, ...)(__VA_ARGS__
)
#define
FRC(R,C) for(int r
=0;r
<R;++r
)for(int c
=0;c
<C;++c
)
template
<class T>
void UPRT(const T _
){if(_
>=10)UPRT(_
/10);PC(_
%10+48);}
#define
UPL(_
) UPRT(_
),PC(10)
template
<class T>
void PRT(const T _
){if(_
<0){PC(45),UPRT<ULL>(-(ULL)_
);return;}if(_
>=10)PRT(_
/10);PC(_
%10+48);}
#define
PL(_
) PRT(_
),PC(10)
#define
MAX(a
, b
) ((a
)>(b
)?(a
):(b
))
#define
MIN(a
, b
) ((a
)<(b
)?(a
):(b
))
constexpr int
MV(6e3+7), ME(MV<<1);
template
<typename cint
>
class Dinic
{
private:
static constexpr cint
CINT_MAX = std
::numeric_limits
<cint
>::max();
struct Ed
{
int ne
, u
, v
;
cint c
;
} ed
[ME];
int head
[MV], cur
[MV], tot
;
int
V, S, T;
int de
[MV];
bool
bfs()
{
static int q
[MV];
int hd
= 0, tl
= 0;
memset(de
, 0, sizeof(*de
) * (V+2));
de
[q
[tl
++]=S] = 1;
while (hd
!= tl
)
{
const int u
= q
[hd
++];
for (int i
=head
[u
]; i
; i
=ed
[i
].ne
)
{
const int v
= ed
[i
].v
;
if (ed
[i
].c
&& !de
[v
])
{
de
[q
[tl
++]=v
] = de
[u
] + 1;
if (v
== T)
return true;
}
}
}
return false;
}
cint
dfs(const int u
, cint
in)
{
if (u
== T)
return in;
cint out
= 0;
for (int i
=cur
[u
]; in&&(cur
[u
]=i
); i
=ed
[i
].ne
)
{
if (ed
[i
].c
>0 && de
[ed
[i
].v
]==de
[u
]+1)
{
const cint tp
= dfs(ed
[i
].v
, MIN(in, ed
[i
].c
));
in -= tp
, out
+= tp
, ed
[i
].c
-= tp
, ed
[i
^1].c
+= tp
;
}
}
if (in || !out
)
de
[u
] = -1;
return out
;
}
public:
void init(const int v
)
{
if (V)
memset(head
, 0, sizeof(*head
) * (V+2));
V = v
;
tot
= 1;
}
void edd(const int u
, const int v
, const cint c
= CINT_MAX)
{
ed
[++tot
].ne
=head
[u
], ed
[tot
].u
=u
, ed
[tot
].v
=v
, ed
[tot
].c
=c
, head
[u
]=tot
;
ed
[++tot
].ne
=head
[v
], ed
[tot
].u
=v
, ed
[tot
].v
=u
, ed
[tot
].c
=0, head
[v
]=tot
;
}
cint
max_flow(const int s
, const int t
)
{
cint sum
= 0;
S = s
, T = t
;
while (bfs())
{
memcpy(cur
, head
, sizeof(*head
) * (V+2));
sum
+= dfs(s
, CINT_MAX);
}
return sum
;
}
};
Dinic
<LL> mf
;
int
main()
{
_IO
get(V, E);
const int
S = 0, T = V+E+1;
mf
.init(T-S+1);
FD(i
, 1, V)
{
get(ai
)
mf
.edd(i
, T, ai
);
}
LL sum
= 0;
FD(i
, 1, E)
{
get(u
, v
, c
)
sum
+= c
;
mf
.edd(V+i
, u
);
mf
.edd(V+i
, v
);
mf
.edd(S, V+i
, c
);
}
PL(sum
- mf
.max_flow(S, T));
#ifdef _KEVIN
getchar();
#endif
return 0;
}
Problem B. Scaygerboss
(待更)
