題干：

鏈接：https://ac.nowcoder.com/acm/contest/369/F
來源：牛客網(wǎng)
?

題目描述

現(xiàn)在你有 n 把靈劍，其中選擇第i把靈劍會(huì)得到的?wiw_iwi??攻擊力。

于此同時(shí)，還有q個(gè)約束，每個(gè)約束形如：

x 和 y?表示兩個(gè)物品的編號(hào)，如果同時(shí)選中可以獲得額外?v0v_0v0??的攻擊力， 同時(shí)不選可以獲得額外?v1v_1v1??點(diǎn)攻擊力，只選擇一個(gè)則會(huì)扣除?v2v_2v2??的攻擊力。

王小D想知道劍陣的最大攻擊力。

九州大陸的未來，必有靈劍山的一筆！

輸入描述:

?

第一行兩個(gè)整數(shù) n, q?，n表示靈劍數(shù)量，q表示約束數(shù)量。

接下來一行，共 n 個(gè)整數(shù)，第 i 個(gè)整數(shù)表示?wiw_iwi?。

接下來 q 行，每行五個(gè)整數(shù)，表示一個(gè)約束。

輸出描述:

共一行，輸出最大的攻擊力。

示例1

輸入

復(fù)制

5 2 4 2 6 6 2 4 2 4 2 2 5 1 6 6 4

輸出

復(fù)制

30

說明

5把靈劍都選 ，獲得4+2+6+6+2+4+6=30的攻擊力

備注:

，且??均為偶數(shù)。

數(shù)據(jù)保證對(duì)于任一無序?qū)?x,y)只會(huì)有一個(gè)約束。

解題報(bào)告：

? 還是看官方題解吧、、、但是注意構(gòu)造的權(quán)值不能出現(xiàn)負(fù)數(shù)，也不知道為什么。（可能是因?yàn)椴蝗徊荒芊诺骄W(wǎng)絡(luò)流里面跑吧？）

另外注意這題不能直接上來就加st到i的邊和i到ed的邊，因?yàn)槟氵@樣的話w[i]會(huì)被計(jì)算多次，不符合定義式，因?yàn)槟阈枰槐贿x擇一次的。

AC代碼：

#include<cstring> #include<cstdio> #include<algorithm> #include<iostream> #define ll long long using namespace std; int n,Q; int tot; struct Edge {int to,ne;ll w; } e[100005 * 2]; int head[10005]; int st,ed; int dis[10050],q[10005];//一共多少個(gè)點(diǎn)跑bfs，dis數(shù)組和q數(shù)組就開多大。 void add(int u,int v,ll w) {e[++tot].to=v; e[tot].w=w; e[tot].ne=head[u]; head[u]=tot;e[++tot].to=u; e[tot].w=0; e[tot].ne=head[v]; head[v]=tot; } bool bfs(int st,int ed) {memset(dis,-1,sizeof(dis));int front=0,tail=0;q[tail++]=st;dis[st]=0;while(front<tail) {int cur = q[front];if(cur == ed) return 1;front++;for(int i = head[cur]; i!=-1; i = e[i].ne) {if(e[i].w&&dis[e[i].to]<0) {q[tail++]=e[i].to;dis[e[i].to]=dis[cur]+1;}}}if(dis[ed]==-1) return 0;return 1; } ll dfs(int cur,ll limit) {//limit為源點(diǎn)到這個(gè)點(diǎn)的路徑上的最小邊權(quán) if(limit==0||cur==ed) return limit;ll w,flow=0;for(int i = head[cur]; i!=-1; i = e[i].ne) { if(e[i].w&&dis[e[i].to]==dis[cur]+1) {w=dfs(e[i].to,min(limit,e[i].w));e[i].w-=w;e[i^1].w+=w;flow+=w;limit-=w;if(limit==0) break;}}if(!flow) dis[cur]=-1;return flow; } ll dinic() {ll ans = 0;while(bfs(st,ed)) ans+=dfs(st,0x7fffffffff);return ans; } ll w[100005]; ll W[100005],W2[100005]; int main() {int Q;cin>>n>>Q;st=n+1,ed=st+1; tot=1;for(int i = 0; i<=ed; i++) head[i] = -1;ll sum = 0,v0,v1,v2,a,b,c,d,e,f;int x,y;for(int i = 1; i<=n; i++) scanf("%lld",w+i),sum += w[i];while(Q--) {scanf("%d%d%lld%lld%lld",&x,&y,&v0,&v1,&v2);sum += v0+v1;a=b=v1/2;c=d=(v0+v1)/2+v2;f=v0/2;e=v0/2;W[x]+=a;W[y]+=b;W2[x]+=e;W2[y]+=f;//add(st,x,a); add(st,y,b); add(x,y,c); add(y,x,d); //add(x,ed,e); add(y,ed,f);}for(int i = 1; i<=n; i++) add(st,i,W[i]),add(i,ed,w[i]+W2[i]);printf("%lld\n",sum - dinic()); return 0; } /* 4 2 1 1 1 1 1 2 4 8 2 2 3 6 8 10 */

不知道為什么還可以這樣建圖（貼一發(fā)別人的代碼）（有空再研究吧）

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e7 + 10; int head[N], rest[N], to[N], flow[N], tot = 1; void sig(int u, int v, int w) {to[++ tot] = v, flow[tot] = w, rest[tot] = head[u], head[u] = tot; } void add(int u, int v, int w) {sig(u, v, w), sig(v, u, 0); } int n, m, cnt, dis[N], S, T; ll ans; int bfs() {for(int i = 1 ; i <= cnt ; ++ i) dis[i] = -1;queue<int> q;q.push(S), dis[S] = 1;while(q.size()) {int u = q.front(); q.pop();for(int i = head[u] ; i ; i = rest[i]) {int v = to[i];if(dis[v] == -1 && flow[i]) {dis[v] = dis[u] + 1;q.push(v);}}}return dis[T] != -1; } int dfs(int u, int f) {if(u == T || !f) return f;int use = 0;for(int i = head[u] ; i ; i = rest[i]) {int v = to[i];if(flow[i] && dis[v] == dis[u] + 1) {int a = dfs(v, min(f - use, flow[i]));flow[i] -= a, flow[i ^ 1] += a;use += a;if(use == f) break;}}if(!use) dis[u] = -1;return use; } int main() {scanf("%d%d", &n, &m);S = ++ cnt, T = ++ cnt;for(int i = 1, a, b ; i <= n ; ++ i) {scanf("%d", &b);a=0;int x = ++ cnt;add(S, x, a);add(x, T, b);ans += a + b;}for(int i = 1, u, v, a, b, c ; i <= m ; ++ i) {scanf("%d%d%d%d%d", &u, &v, &b, &a, &c);u += 2, v += 2;int x = ++ cnt, y = ++ cnt;add(S, x, a); add(x, u, a); add(x, v, a);add(u, y, b); add(v, y, b); add(y, T, b);add(u, v, c); add(v, u, c);ans += a + b;}while(bfs()) {ans -= dfs(S, 0x3f3f3f3f);}printf("%lld\n", ans); }

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 369F】小D的剑阵（最小割建图，二元关系建图，网络流最小割）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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