題干：

題目描述

小B有n個下屬，現小B要帶著一些下屬讓別人拍照。

有m個人，每個人都愿意付給小B一定錢讓n個人中的一些人進行合影。如果這一些人沒帶齊那么就不能拍照，小B也不會得到錢。

注意：帶下屬不是白帶的！！！對于每個下屬，如果他帶了那么小B需要給他一些錢，保證當他拍照時配合。

請問，小B的凈收益最多是多少。

輸入輸出格式

輸入格式：

?

第1行有2個正整數m和n（0<m,n<=100）。接下來的m行，每行是一個要求拍照的人的有關數據。第一個數是他同意支付該合影的費用；接著是該合影需要的若干下屬的編號，以一個0作為行的結束標記。最后一行的n個數是帶每個下屬的費用。

?

輸出格式：

?

一個數，表示最大收益。小B可以一個人也不帶。

?

輸入輸出樣例

輸入樣例#1：?復制

2 3 10 1 2 0 25 2 3 0 5 6 7

輸出樣例#1：?復制

17

說明

對于10%的數據每個人都要求讓全部n個人合影

對于30%的數據n<=15 m<=15

另有10%的數據答案為0

對于50%的數據n<=40 m<=40

另有10%的數據每個人只愿意拍一個人

對于100%的數據m,n<=100

解題報告：

? ?最大權閉合圖裸題。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 5e3 + 5; int n,m; int tot; const ll INF = 0x3f3f3f3f3f3f3f3f; struct Edge {int to,ne;ll w; } e[MAX*20]; int head[MAX]; int st,ed; ll a[MAX],dis[MAX],q[MAX];//一共多少個點跑bfs，dis數組和q數組就開多大。 void add(int u,int v,ll w) {e[++tot].to=v;e[tot].w=w;e[tot].ne=head[u];head[u]=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為源點到這個點的路徑上的最小邊權 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,INF);return ans; } int ans2; bool vis[MAX]; void dfs2(int cur) {if(cur == ed) return;vis[cur] = 1;ans2++;for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].to;if(e[i].w == 0 || vis[v]) continue;dfs2(v);} } int main() {cin>>m>>n;st=0;ed=n+m+1;tot=1;ll sum = 0;for(int i = 0; i<=n+m+1; i++) head[i] = -1;for(int x,y,i = 1; i<=m; i++) {scanf("%d",&x);sum += x;add(st,i,x);add(i,st,0);while(scanf("%d",&y) && y) {add(i,m+y,INF);add(m+y,i,0);}}for(int x,i = 1; i<=n; i++) {scanf("%d",&x);add(m+i,ed,x);add(ed,m+i,0);}ll ans = sum - dinic();cout << ans << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的【洛谷 - P3410】拍照（最大权闭合图，网络流最小割）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。