題目鏈接

題意

每個(gè)人可以選擇兩種角色$(A,B)$，給定$M$個(gè)關(guān)系$(x,y)$，如果$x,y$同時(shí)選擇$A$總的攻擊力加$a$，如果$x,y$同時(shí)選擇$B$總的攻擊力加$c$，如果$x,y$分別選擇$A，B$總的攻擊力加$c$，求如何分配使得總的攻擊力最大？

思路

轉(zhuǎn)化為最小割模型，統(tǒng)計(jì)所有流量，構(gòu)造使得最小割為多加的流量，邊權(quán)擴(kuò)大2倍，防止小數(shù)。
(來(lái)自題解)

設(shè)一條邊的三種貢獻(xiàn)為 $A，B，C$，可以得到以下方程：

$a+b=A+B$（$x，y$ 都選 Mage）

$c+d=C+B$（$x，y$ 都選 Warrior）

$a+d+e=A+C$（$x$ 選 Mage， $y$ 選 Warrior ）

$b+c+e=A+C$（$x$ 選 Warrior， $y$ 選 Mage ）

可得一組解 $a=b=（A+B）/2，c=d=(C+B)/2,e=?B+(A+C)/2$ ，然后將所有有關(guān)系的兩點(diǎn)的圖合并，用所有貢獻(xiàn)減掉這個(gè)圖的最小割即可。

#include <bits/stdc++.h> #define endl '\n' const int maxn = 5e2 + 5; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; struct Dinic{struct ac{int v, c, nex;}edge[maxn << 7]; // 根據(jù)題目要求計(jì)算int s, e;int head[maxn], dis[maxn], curedge[maxn], cnt;void init() {cnt = 0;memset(head, -1, sizeof(head));}void add(int u, int v, int c) {// 正向建邊edge[cnt] = {v, c, head[u]};head[u] = cnt++;// 反向建邊, 流量為0edge[cnt] = {u, 0, head[v]};head[v] = cnt++;}bool bfs() {queue<int> que;que.push(s);memset(dis, 0, sizeof(dis)); // 對(duì)圖進(jìn)行分層dis[s] = 1;while (!que.empty()) {int u = que.front();que.pop();for (int i = head[u]; i != -1; i = edge[i].nex) {int v = edge[i].v;int c = edge[i].c;// 如果節(jié)點(diǎn)v已經(jīng)分過(guò)層或者u->v流量為0, continueif (dis[v] || c == 0) continue;dis[v] = dis[u] + 1; // 對(duì)v進(jìn)行標(biāo)記并加入隊(duì)列que.push(v);}}return dis[e] > 0; // 判斷是否存在增廣路，s是否能到達(dá)e}int dfs(int u, int flow) { // 增廣路走到u點(diǎn)的最小流量為flowif (u == e || flow == 0) return flow;// 遍歷u的所有出邊for (int &i = curedge[u]; i != -1; i = edge[i].nex) { // 當(dāng)前弧優(yōu)化int v = edge[i].v;int c = edge[i].c;// 判斷能否u->v增廣if (dis[v] != dis[u] + 1 || c == 0) continue;int d = dfs(v, min(flow, c));if (d > 0) { // 找到一條增廣路，修改增廣路上的正反向邊edge[i].c -= d;edge[i^1].c += d;return d;} }dis[u] = -1; // // 炸點(diǎn)優(yōu)化return 0;}long long dinic() {long long sum = 0, d;while (bfs()) { // 判讀是否存在增廣路for (int i = 0; i <= e; ++i) curedge[i] = head[i]; // copy head數(shù)組，在dfs中可以直接得到下一條沒(méi)有被增廣過(guò)的邊while ((d = dfs(s, inf)) > 0) sum += d; // 多次dfs找增廣路}return sum;} }D; int L[maxn], R[maxn]; int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m, s, e;while (scanf("%d %d", &n, &m) != EOF) {D.s = s = 0, D.e = e = n + 1;D.init();int u, v, a, b, c;long long ans = 0;fill(L, L+n+1, 0);fill(R, R+n+1, 0);for (int i = 0; i < m; ++i) {scanf("%d %d %d %d %d", &u, &v, &a, &b, &c);ans += a + b + c;D.add(u, v, a + c - 2*b);D.add(v, u, a + c - 2*b);L[u] += b + c;L[v] += b + c;R[u] += a + b;R[v] += a + b;}for (int i = 1; i <= n; ++i) {D.add(s, i, L[i]);D.add(i, e, R[i]);}ans = ans * 2 - D.dinic();printf("%lld\n", ans / 2);}return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的HDU - 6598 Harmonious Army (最小割)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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