題目大意：一張無向圖$G=(V,E)$，定義$f(G)=\sum\limits_{e\in E}w_e-\sum\limits_{v\in V}w_v$，給一張$n(n\leqslant10^3)$個點$m(m\leqslant10^3)$條邊的無向圖，求$\max_{G'\in G}\{f(G')\}$。

題解：最大權(quán)閉合子圖。

源點往有代價物品連其邊權(quán)為其代價的邊。

有代價物品往選了它可能產(chǎn)生收益的組連邊權(quán)為的邊。

每個組往匯點連邊權(quán)為其收益的邊。

由源點向原圖中的每條邊連一條容量為其收益的邊，原圖中的邊向它的兩個端點連容量為$\infty$的邊，原圖中的每個點向匯點連容量為其代價的邊

把總收益減去最小割即可

卡點：無

?

C++ Code：

#include <algorithm> #include <cstdio> #define maxn 1010 #define maxm 1010 const int N = maxn + maxm, M = N + 2 * maxm; const int inf = 0x3f3f3f3f;namespace Network_Flow {int lst[N], head[N], cnt = 1;struct Edge {int to, nxt, w;} e[M << 1];inline void addedge(int a, int b, int c) {e[++cnt] = (Edge) { b, head[a], c }; head[a] = cnt;e[++cnt] = (Edge) { a, head[b], 0 }; head[b] = cnt;}long long MF;int n, st, ed;int GAP[N], d[N];int q[N], h, t;void init() {GAP[d[ed] = 1] = 1;for (int i = 0; i < n; ++i) lst[i] = head[i];q[h = t = 0] = ed;while (h <= t) {int u = q[h++];for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if (!d[v]) {d[v] = d[u] + 1;++GAP[d[v]];q[++t] = v;}}}}int dfs(int u, int low) {if (!low || u == ed) return low;int w, res = 0;for (int &i = lst[u]; i; i = e[i].nxt) if (e[i].w) {int v = e[i].to;if (d[u] == d[v] + 1) {w = dfs(v, std::min(low, e[i].w));res += w, low -= w;e[i].w -= w, e[i ^ 1].w += w;if (!low) return res;}}if (!(--GAP[d[u]])) d[st] = n + 1;++GAP[++d[u]], lst[u] = head[u];return res;}void ISAP(int S, int T) {st = S, ed = T;init();while (d[st] <= n) MF += dfs(st, inf);} } using Network_Flow::addedge;int n, m; long long sum; int main() {scanf("%d%d", &n, &m); Network_Flow::n = n + m + 2;int st = 0, ed = n + m + 1;for (int i = 1, x; i <= n; ++i) {scanf("%d", &x);addedge(st, i, x);}for (int i = 1, a, b, c; i <= m; ++i) {scanf("%d%d%d", &a, &b, &c);addedge(a, n + i, inf);addedge(b, n + i, inf);addedge(n + i, ed, c);sum += c;}Network_Flow::ISAP(st, ed);printf("%lld\n", sum - Network_Flow::MF);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Memory-of-winter/p/10341430.html

總結(jié)

以上是生活随笔為你收集整理的[CF1082G]Petya and Graph的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。