[LibreOJ 2100][TJOI2015]线性代数
颓一波式子可以发现答案就是\(ABA^T-CA^T\)。然后发现对于一个\(B\)中的元素\(B_{i, j}\)要对答案做出贡献要求\(A_i\)和\(A_j\)都为1，而\(A_i\)为1会导致答案减去一个\(C_i\)。
因此我们可以分别对\(B\)中元素和\(A\)中元素建点。\(B\)中元素会带来收益，但是要求依赖两个\(A\)中元素。而\(A\)中元素会带来一定的笋丝。这个就已经事很明显的最大权闭合子图力，，，
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 505;
const int maxno = 500 * 500 + 500 + 5;
const int maxm = 2 * (500 * 500 * 3 + 500 + 5);
int first[maxno];
int next[maxm], to[maxm], flow[maxm], cap[maxm];
int gcnt = 0;
void add_edge(int u, int v, int c) {
gcnt ++;
next[gcnt] = first[u]; first[u] = gcnt;
to[gcnt] = v; cap[gcnt] = c; flow[gcnt] = 0;
}
void ins_edge(int u, int v, int c) {
add_edge(u, v, c); add_edge(v, u, 0);
}
int rev(int i) {
if(1 & i) {
return i + 1;
} else {
return i - 1;
}
}
int d[maxno];
int s, t, num;
bool bfs() {
static bool vis[maxno];
std::fill(vis, vis + num + 1, false);
std::fill(d, d + num + 1, 0);
std::queue<int> Q; Q.push(s);
d[s] = 1; vis[s] = true;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = first[u]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && cap[i] > flow[i]) {
d[v] = d[u] + 1;
Q.push(v); vis[v] = true;
}
}
}
return vis[t];
}
int cur[maxno];
int dfs(int x, int a) {
if(a == 0 || x == t) return a;
int ret = 0;
for(int &i = cur[x]; i; i = next[i]) {
int v = to[i], f;
if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
ret += f; a -= f;
flow[i] += f; flow[rev(i)] -= f;
if(a == 0) break;
}
}
if(a > 0) d[x] = -1;
return ret;
}
int dinic() {
int ret = 0;
while(bfs()) {
for(int i = 0; i <= num; i ++) cur[i] = first[i];
ret += dfs(s, 0x7f7f7f7f);
}
return ret;
}
int n;
int main() {
int ans = 0;
scanf("%d", &n);
s = 0, t = n * n + n + 1;
num = t;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n; j ++) {
int u = (i - 1) * n + j; int val; scanf("%d", &val);
ans += val; ins_edge(s, u, val);
ins_edge(u, n * n + i, 0x7f7f7f7f);
ins_edge(u, n * n + j, 0x7f7f7f7f);
}
}
for(int i = 1; i <= n; i ++) {
int val; scanf("%d", &val);
ins_edge(n * n + i, t, val);
}
ans -= dinic();
printf("%d\n", ans);
return 0;
}
[洛谷 P4177][CEOI2008]order
啊啊啊只会做水题了……
很显然是最小割吧……长得很像最大权闭合子图，但又不一样的。
那么就把最大权闭合子图中的无穷边（我称之为违约边）的费用改成租用的费用。这样一来，如果选了计划（不割计划）还不购买机器（割去机器），那就只能支付租金了（割违约边）。
这其实也算是一种套路了吧？觉得以前见过很多次但是有很多叫法……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
const int maxn = 200005;
const int maxm = 2000005;
const int maxe = maxm << 2;
int n, m;
int first[maxn];
int next[maxe], to[maxe], flow[maxe], cap[maxe];
int gcnt = 0;
inline void add_edge(int u, int v, int f) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
to[gcnt] = v;
flow[gcnt] = 0; cap[gcnt] = f;
}
inline int rev(int i) {
return (((i - 1) ^ 1) + 1);
}
inline void ins_edge(int u, int v, int f) {
add_edge(u, v, f);
add_edge(v, u, 0);
}
int d[maxn];
int s, t, tot;
inline bool bfs() {
static bool vis[maxn];
std::fill(vis, vis + 1 + tot, false);
std::fill(d, d + 1 + tot, 0);
std::queue<int> Q;
Q.push(s); vis[s] = true; d[s] = 1;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = first[u]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && cap[i] > flow[i]) {
d[v] = d[u] + 1; vis[v] = true;
Q.push(v);
}
}
}
return vis[t];
}
int cur[maxn];
int dfs(int x, int a) {
if(a == 0 || x == t) return a;
int ans = 0;
for(int &i = cur[x]; i; i = next[i]) {
int v = to[i];
int f;
if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
ans += f; a -= f;
flow[i] += f; flow[rev(i)] -= f;
if(a == 0) break;
}
}
if(a > 0) d[x] = -1;
return ans;
}
int dinic() {
int ans = 0;
while(bfs()) {
for(int i = 0; i <= tot; i ++) cur[i] = first[i];
ans += dfs(s, 0x7fffffff);
}
return ans;
}
int main() {
int n, m; scanf("%d%d", &n, &m);
s = 0; t = tot = n + m + 1;
int ans = 0;
for(int i = 1; i <= n; i ++) {
int w, p; scanf("%d%d", &w, &p);
ins_edge(s, i, w); ans += w;
for(int j = 1; j <= p; j ++) {
int id, co; scanf("%d%d", &id, &co);
ins_edge(i, id + n, co);
}
}
for(int i = n + 1; i <= n + m; i ++) {
int co; scanf("%d", &co);
ins_edge(i, t, co);
}
printf("%d\n", ans - dinic());
return 0;
}
[BZOJ 2561]最小生成树
窝只会做水体了qwq
因为这条边既存在在最大生成树里，又存在在最小生成树里。那就说明\(u\)到\(v\)的路径上，在最大生成树上这条边是最小的，在最小生成树上这条边是最大的。
所以说我们不能用大于\(L\)的边来联通\(u\)和\(v\)，也不能用小于\(L\)的边，于是乎……跑两次最小割即可。
代码：
/**************************************************************
Problem: 2561
User: danihao123
Language: C++
Result: Accepted
Time:1528 ms
Memory:15952 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
const int maxn = 20005;
const int maxm = 200005;
const int maxe = maxm << 2;
int n, m;
int first[maxn];
int next[maxe], to[maxe], flow[maxe], cap[maxe];
int gcnt = 0;
inline void init_graph() {
gcnt = 0;
std::fill(first + 1, first + 1 + n, 0);
}
inline void add_edge(int u, int v, int f) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
to[gcnt] = v;
flow[gcnt] = 0; cap[gcnt] = f;
}
inline int rev(int i) {
return (((i - 1) ^ 1) + 1);
}
inline void ins_edge(int u, int v, int f) {
add_edge(u, v, f);
add_edge(v, u, 0);
}
int line[maxm][3];
int d[maxn];
int s, t;
inline bool bfs() {
static bool vis[maxn];
std::fill(vis + 1, vis + 1 + n, false);
std::fill(d + 1, d + 1 + n, 0);
std::queue<int> Q;
Q.push(s); vis[s] = true; d[s] = 1;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = first[u]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && cap[i] > flow[i]) {
d[v] = d[u] + 1; vis[v] = true;
Q.push(v);
}
}
}
return vis[t];
}
int cur[maxn];
int dfs(int x, int a) {
if(a == 0 || x == t) return a;
int ans = 0;
for(int &i = cur[x]; i; i = next[i]) {
int v = to[i];
int f;
if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
ans += f; a -= f;
flow[i] += f; flow[rev(i)] -= f;
if(a == 0) break;
}
}
if(a > 0) d[x] = -1;
return ans;
}
int dinic() {
int ans = 0;
while(bfs()) {
for(int i = 1; i <= n; i ++) cur[i] = first[i];
ans += dfs(s, 0x7fffffff);
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int *l = line[i];
scanf("%d%d%d", &l[0], &l[1], &l[2]);
}
int L; scanf("%d%d%d", &s, &t, &L);
for(int i = 1; i <= m; i ++) {
int *l = line[i];
if(l[2] < L) {
ins_edge(l[0], l[1], 1);
ins_edge(l[1], l[0], 1);
}
}
int ans = dinic();
init_graph();
for(int i = 1; i <= m; i ++) {
int *l = line[i];
if(l[2] > L) {
ins_edge(l[0], l[1], 1);
ins_edge(l[1], l[0], 1);
}
}
ans += dinic();
printf("%d\n", ans);
return 0;
}
[BZOJ 3158]千钧一发
好有意思的题呢qwq
首先观察到一点，我们可以把所有装置按照\(a_i\)的奇偶性进行分类（也可以说是黑白染色？）。容易发现任意偶数的最大公约数都至少是2，所以任意偶数间不会互相冲突。然后任意两个奇数的平方和一定不是完全平方数，可以这么证一下（感谢金爷！）：
那两个奇数可以分别设成\(2x + 1\)和\(2y + 1\)，然后他们的平方和就是\(4(x^2 + y^2 + x + y) + 2\)。然后思考一点，就是一个奇数的平方一定是奇数，所以说那个平方和是一个偶数。但是，如果一个完全平方数是偶数，那么它的算术平方根一定是偶数。然而，一个偶数的平方一定是4的倍数。但我们求出的平方和膜4得2，所以不行。
所以说冲突只存在于奇偶性不同的数中。然后用无限大的边来表示冲突关系，最小割高一波即可。
代码（常数卡卡卡……只能用pb_ds的蛤希表了）：
/**************************************************************
Problem: 3158
User: danihao123
Language: C++
Result: Accepted
Time:9676 ms
Memory:130460 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
typedef long long ll;
ll gcd(ll a, ll b) {
if(!b) {
return a;
} else {
return gcd(b, a % b);
}
}
__gnu_pbds::gp_hash_table<ll, bool> S2;
void process_S2() {
for(ll i = 1LL; i * i <= 2000000000000LL; i ++) {
S2[i * i] = true;
}
}
const int maxno = 1050;
const int maxm = 2000500;
int first[maxno];
int next[maxm], to[maxm], cap[maxm], flow[maxm];
int gcnt = 0;
void add_edge(int u, int v, int f) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
to[gcnt] = v;
cap[gcnt] = f;
flow[gcnt] = 0;
}
int rev(int i) {
if(1 & i) {
return i + 1;
} else {
return i - 1;
}
}
void ins_edge(int u, int v, int f) {
add_edge(u, v, f); add_edge(v, u, 0);
}
int n;
int s, t;
int d[maxno];
bool bfs() {
static bool vis[maxno];
memset(vis, 0, sizeof(vis));
d[s] = 1; vis[s] = true;
std::queue<int> Q; Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = first[u]; i; i = next[i]) {
int v = to[i];
if(cap[i] > flow[i] && !vis[v]) {
d[v] = d[u] + 1; vis[v] = true;
Q.push(v);
}
}
}
return vis[t];
}
int cur[maxno];
int dfs(int u, int a) {
if(a == 0 || u == t) return a;
int fl = 0;
for(int &i = cur[u]; i; i = next[i]) {
int v = to[i]; int f;
if(d[v] == d[u] + 1 && (f = dfs(v, std::min(cap[i] - flow[i], a))) > 0) {
fl += f; a -= f;
flow[i] += f; flow[rev(i)] -= f;
if(a == 0) break;
}
}
if(a > 0) d[u] = -1;
return fl;
}
int tot;
int dinic() {
int ans = 0;
while(bfs()) {
for(int i = 0; i <= tot; i ++) cur[i] = first[i];
ans += dfs(s, 0x7fffffff);
}
return ans;
}
const int maxn = 1005;
ll A[maxn]; int B[maxn];
int main() {
process_S2();
scanf("%d", &n); tot = n + 1;
s = 0, t = tot;
std::vector<int> odd, even;
for(int i = 1; i <= n; i ++) {
scanf("%lld", &A[i]);
if(1LL & A[i]) {
odd.push_back(i);
} else {
even.push_back(i);
}
}
int ans = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", &B[i]); ans += B[i];
if(1LL & A[i]) {
ins_edge(i, t, B[i]);
} else {
ins_edge(s, i, B[i]);
}
}
for(int i = 0; i < even.size(); i ++) {
int p1 = even[i];
for(int j = 0; j < odd.size(); j ++) {
int p2 = odd[j];
if(gcd(A[p1], A[p2]) == 1LL && S2.find(A[p1] * A[p1] + A[p2] * A[p2]) != S2.end()) {
ins_edge(p1, p2, 0x7f7f7f7f);
}
}
}
ans -= dinic();
printf("%d\n", ans);
return 0;
}
[LibreOJ 2146][SHOI2017]寿司餐厅
建了半天图……搞出来了几个神奇的最小割……
然后发现这TM不就是最简单的最大权闭合子图吗……
首先和正负点权普通的最大权闭合子图一样，然后任意\(d_{i, i}\)去依赖点\(i\)。对于一个\(d_{i, j}(i < j)\)，我们要保证那一天\([i, j]\)全部被吃了，所以说它需要依赖\(d_{i + 1, j}\)和\(d_{i, j - 1}\)。
每种寿司的费用也不难处理，我们把\(mx^2\)和\(cx\)分开考虑。\(mx^2\)单独建点，很显然代号为所有\(x\)都要依赖它。对于\(cx\)，可以视为所有点有一个\(x\)的费用。
然后van了……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 5000005;
const int maxm = 5000005;
int first[maxn];
int next[maxm], to[maxm], cap[maxm], flow[maxm];
int gcnt = 0;
void add_edge(int u, int v, int f) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
to[gcnt] = v;
cap[gcnt] = f;
flow[gcnt] = 0;
}
int rev(int i) {
if(1 & i) {
return i + 1;
} else {
return i - 1;
}
}
void ins_edge(int u, int v, int f) {
add_edge(u, v, f); add_edge(v, u, 0);
}
int s, t;
int d[maxn];
bool bfs() {
#ifdef LOCAL
// puts("A new round :");
#endif
static bool vis[maxn];
memset(vis, 0, sizeof(vis));
d[s] = 1; vis[s] = true;
std::queue<int> Q; Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = first[u]; i; i = next[i]) {
int v = to[i];
if(cap[i] > flow[i] && !vis[v]) {
d[v] = d[u] + 1; vis[v] = true;
#ifdef LOCAL
// printf("d[%d] : %d\n", v, d[v]);
#endif
Q.push(v);
}
}
}
return vis[t];
}
int cur[maxn];
int dfs(int u, int a) {
#ifdef LOCAL
// printf("State (%d, %d)\n", u, a);
#endif
if(a == 0 || u == t) return a;
int fl = 0;
for(int &i = cur[u]; i; i = next[i]) {
int v = to[i]; int f;
if(d[v] == d[u] + 1 && (f = dfs(v, std::min(cap[i] - flow[i], a))) > 0) {
fl += f; a -= f;
flow[i] += f; flow[rev(i)] -= f;
if(a == 0) break;
}
}
if(a > 0) d[u] = -1;
return fl;
}
int tot;
int dinic() {
int ans = 0;
while(bfs()) {
for(int i = 0; i <= tot; i ++) cur[i] = first[i];
ans += dfs(s, 0x7fffffff);
}
return ans;
}
int ma_p[105], ma_m[1005];
int ma_d[105][105];
int main() {
tot = 1;
int n, m; scanf("%d%d", &n, &m);
int ans = 0;
s = 0, t = 1;
for(int i = 1; i <= n; i ++) {
int a; scanf("%d", &a);
ma_p[i] = ++ tot;
#ifdef LOCAL
printf("p[%d] : %d\n", i, tot);
#endif
if(!ma_m[a]) {
ma_m[a] = ++ tot;
#ifdef LOCAL
printf("m[%d] : %d\n", a, tot);
#endif
ins_edge(tot, 1, m * a * a);
}
ins_edge(ma_p[i], 1, a);
ins_edge(ma_p[i], ma_m[a], 0x7fffffff);
}
for(int i = 1; i <= n; i ++) {
ma_d[i][i] = ++ tot;
for(int j = i + 1; j <= n; j ++) {
ma_d[i][j] = ++ tot;
#ifdef LOCAL
printf("ma_d[%d][%d] : %d\n", i, j, tot);
#endif
}
}
for(int i = 1; i <= n; i ++) {
int d_i; scanf("%d", &d_i);
if(d_i >= 0) {
ans += d_i;
ins_edge(0, ma_d[i][i], d_i);
} else {
ins_edge(ma_d[i][i], 1, -d_i);
}
ins_edge(ma_d[i][i], ma_p[i], 0x7fffffff);
for(int j = i + 1; j <= n; j ++) {
scanf("%d", &d_i);
int np = ma_d[i][j];
if(d_i >= 0) {
ans += d_i;
ins_edge(0, np, d_i);
ins_edge(np, ma_d[i][j - 1], 0x7fffffff);
ins_edge(np, ma_d[i + 1][j], 0x7fffffff);
} else {
ins_edge(np, 1, -d_i);
ins_edge(np, ma_d[i][j - 1], 0x7fffffff);
ins_edge(np, ma_d[i + 1][j], 0x7fffffff);
}
}
}
ans -= dinic();
#ifdef LOCAL
for(int i = 0; i <= tot; i ++) {
for(int j = first[i]; j; j = next[j]) {
if(!(j & 1)) continue;
int v = to[j];
if(cap[j] == flow[j]) {
printf("Edge (%d, %d, %d) deleted.\n", i, v, cap[j]);
}
}
}
#endif
printf("%d\n", ans);
return 0;
}
[COGS 727]太空飞行计划
第一次做最大权闭合图……so sad
关于最大权闭合图的做法，可以参考胡伯涛前辈的《最小割模型在信息学竞赛中的应用》。不过很麻烦的事是……打印方案。
注意，割走的边要么和[tex]S[/tex]相连，要么就和[tex]T[/tex]相连。如果一条从[tex]S[/tex]到[tex]E_i[/tex]被割走了，那么就说明[tex]E_i[/tex]没有被选择；如果一条从[tex]I_i[/tex]到[tex]T[/tex]的边被割走了，那么就说明[tex]I_i[/tex]被选择了。
于是乎，Dinic最后一次造层次图的时候（这次最终将不能到达[tex]T[/tex]），如果某个点（除了[tex]S[/tex]和[tex]T[/tex]）被访问到了，那个点就被选择了。
最小割的结果是所有拒绝的实验的能赚的钱及所有选用的仪器消耗的钱的和。也就是说，答案就是[tex]p[/tex]的和减去最小割。
代码：
#include <cstdio>
#include <iostream>
#include <iterator>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn=211;
const int INF=0x7fffffff;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
struct Edge{
int u,v,cap,flow;
};
namespace Dinic{
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Mincut(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,INF);
}
return ans;
}
};
vector<int> AnsList;
int main(){
register int i,j,ans=0;
int m,n,p,x;
bool flag;
string line;
// ios::sync_with_stdio(false);
// cin.tie(0);
freopen("shuttle.in","r",stdin);
freopen("shuttle.out","w+",stdout);
ostream_iterator<int> output(cout," ");
scanf("%d %d\n",&m,&n);
REP_B(i,m){
getline(cin,line);
stringstream ss(line);
ss>>p;
ans+=p;
Dinic::AddEdge(0,i,p);
while(ss>>x){
Dinic::AddEdge(i,m+x,INF);
}
}
REP_B(i,n){
cin>>p;
Dinic::AddEdge(i+m,n+m+1,p);
}
ans-=Dinic::Mincut(0,n+m+1);
REP_B(i,m){
if(Dinic::vis[i]){
AnsList.push_back(i);
}
}
copy(AnsList.begin(),AnsList.end(),output);
cout<<endl;
AnsList.clear();
REP_B(i,n){
if(Dinic::vis[i+m]){
AnsList.push_back(i);
}
}
copy(AnsList.begin(),AnsList.end(),output);
cout<<endl;
cout<<ans<<endl;
return 0;
}
[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查
这个是一道题啊……不过都是挺经典的问题……
建图是这样的：支持0的从[tex]S[/tex]向此点连一条容量为1的边，支持1的就向[tex]T[/tex]连一条长度为1的边，朋友之间连一条长度为1的边。跑一遍最小割即可。
这个的解释？最优情况下任何人违背自己的意见都是因为怕和朋友冲突，和朋友冲突则是因为没有违背自己的意见（废话）。所以拆了最小割就解决掉了所有冲突问题。
代码：
/**************************************************************
Problem: 2768
User: danihao123
Language: C++
Result: Accepted
Time:60 ms
Memory:7668 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=305;
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int s,t;
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int cur[maxn],d[maxn];
bool bfs(){
register int i,u;
queue<int> Q;
memset(vis,0,sizeof(vis));
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
d[e.v]=d[u]+1;
Q.push(e.v);
vis[e.v]=true;
}
}
}
return vis[t];
}
int dfs(int x,int a){
if(x==t || a==0)
return a;
int f,flow=0;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){
flow+=f;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
a-=f;
if(a==0)
break;
}
}
return flow;
}
int MinCut(int S,int T){
register int ans=0;
s=S;
t=T;
while(bfs()){
memset(cur,0,sizeof(cur));
ans+=dfs(s,0x7fffffff);
}
return ans;
}
};
int main(){
int n,m;
int u,v;
register int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&u);
if(!u){
Dinic::AddEdge(0,i,1);
}else{
Dinic::AddEdge(i,n+1,1);
}
}
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
Dinic::AddEdge(u,v,1);
Dinic::AddEdge(v,u,1);
}
printf("%d\n",Dinic::MinCut(0,n+1));
return 0;
}
[BZOJ 1001]狼抓兔子
终于A了！
再给大家欣赏一下zzs这个逗比百折不挠的卡评记录（一页半慎看）：
这道题就是平面图转对偶图的恶心题~
zzs在此列出此题坑点，望后人警觉：
- 最好写一个定位函数，不然点的位置很容易混。
- 不要用SPFA，不然会被卡。
- m等于1或n等于1的情况需要特判！
- 不要用边表，内存开销太惊人……
- 用邻接表的话，不要像zzs这个逗比一样开小内存……
代码：
