第一次做最小割，不是很理解。

https://www.luogu.org/problemnew/show/P1361

要把東西分進兩類里，好像可以應用最小割的模板，其中一類A作為源點，另一類B作為匯點，價值就是邊的容量。

然后最小割一定會割斷每個中間結點的兩邊的其中一邊，這樣最大價值就順帶求出來了。

?

在這道題里面額外還有某些點成組出現的額外價值。題解的辦法是分別虛擬兩個結點代表兩個集合，源點到集合a的容量是其價值，然后從a連到他的附屬結點各邊容量為無窮。無窮的邊不能被最小割割斷。所以要么是把a的從屬結點到t的邊全部割斷，然后多出來a的附加價值，要么是把s到a的附加價值邊割斷使a不能流向t。畫個圖發現很巧妙。

?

轉載自：https://www.luogu.org/blog/ButterflyDew/solution-p1361

?這個屬于最大權閉合子圖，意思是某個節點（集合）若被選中則它的從屬結點都要被選中，這種情況就原圖建無窮流量邊，各正權點連S容量為權，負權點連T容量為權的絕對值。答案=所有正權點的和-最小割。

?

當最小割割斷右邊的負權點的邊的時候意味著你付出相應的代價購買它留在左邊，當最小割割斷左邊的時候意味著你舍棄了他的價值但是也不用付出割斷他的代價。

?

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e6+5,M=2e6+5; int n,m,s,t,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];void add(int u,int v,int w) {ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w; }void addedge(int u,int v,int w) {add(u,v,w),add(v,u,0); }int bfs(int s,int t) {memset(dep,0,sizeof(dep));memcpy(cnr,lnk,sizeof(lnk));std::queue<int> q;q.push(s),dep[s]=1;while(!q.empty()) {int u=q.front(); q.pop();for(int i=lnk[u];i;i=nxt[i]) {int v=ter[i];if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;}}return dep[t]; }int dfs(int u,int t,int flow) {if(u==t) return flow;int ans=0;for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {cnr[u]=i;int v=ter[i];if(val[i]&&dep[v]==dep[u]+1) {int x=dfs(v,t,std::min(val[i],flow-ans));if(x) val[i]-=x,val[i^1]+=x,ans+=x;}}if(ans<flow) dep[u]=-1;return ans; }ll dinic(int s,int t) {ll ans=0;while(bfs(s,t)) {ll x;while((x=dfs(s,t,1<<30))) ans+=x;}return ans; }int main() {ll sum=0;scanf("%d",&n);s=0,t=10000;for(int i=1;i<=n;i++){int u=s,v=i,w;scanf("%d",&w);addedge(u,v,w);sum+=w;}for(int i=1;i<=n;i++){int u=i,v=t,w;scanf("%d",&w);addedge(u,v,w);sum+=w;}int m;scanf("%d",&m);int id=n+1;while(m--) {int k;scanf("%d",&k);int w1,w2;scanf("%d%d",&w1,&w2);addedge(s,id,w1);addedge(id+1,t,w2);sum+=w1+w2;for(int i=0;i<k;i++){int x;scanf("%d",&x);addedge(id,x,0x3f3f3f3f);addedge(x,id+1,0x3f3f3f3f);}id+=2;}printf("%lld\n",sum-dinic(s,t));return 0; }

?

轉載于:https://www.cnblogs.com/Yinku/p/10618586.html

總結

以上是生活随笔為你收集整理的洛谷 - P1361 - 小M的作物 - 最小割 - 最大权闭合子图的全部內容，希望文章能夠幫你解決所遇到的問題。

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