P3973 TJOI2015 線性代數 最小割

2022-09-22 20:48:01 字數 1184 閱讀 1684

戳這裡

\[d=\sum_^na_\times (\sum_^na_b_-c_)

\]我們觀察式子可以發現 \(b_\) 會被選當且僅當 \(a_,a_\) 都為 1,\(-c_\) 會被選當且僅當 \(a_\) 為 1

也就是說 \(b_\) 和 \(-c_,-c_\) 必須同時存在,也就是說選了 \(b_\) 就得減少 \(c_+c_\) 這個東西好像很最小割,我們只要把 \(b_\) 到匯點路徑上的流量表示為 \(c_+c_\) 那麼要麼不選 \(b_\) 要麼必須減少 \(c_+c_\)

具體做法就是:

對於每一個 \(b_,c_\) 建立一個點

源點向所有的 \(b_\) 連一條流量為 \(b_\) 的邊,\(c_\) 向匯點連一條流量為 \(c_\) 的邊

每一個 \(b_\) 向 \(c_,c_\) 連一條流量為 \(\inf\) 的邊

求最小割,答案等於 \(\sum b_-mincut\)

#include#define inl inline

#define reg register

#define id(i,j) (i-1)*n+j

using namespace std;

namespace zzc

while(isdigit(ch))

return x*f;

}const ll maxn = 3e5+5;

const ll inf = 0x3f3f3f3f3f3f3f3f;

ll n,cnt=1,st,ed,ans;

ll head[maxn],dep[maxn],cur[maxn];

queueq;

struct edge

e[maxn<<3];

inl void add(ll u,ll v,ll w)

inl void add_edge(ll u,ll v,ll w)

inl bool bfs()}}

return dep[ed]!=-1;

}ll dfs(ll u,ll flow)

}if(!used) dep[u]=-1;

return used;

}inl void dinic()

}void work()

}int main()

P3973 TJOI2015 線性代數

洛谷 給你一個 n times n 的矩陣 b 和一個 1 times n 的矩陣 c 讓你求一個 1 times n 的 01 矩陣 a...