這題是一道最大權閉合圖的經典難題（by Rose_max)

upd：不誤人子弟了，這就是一個裸的最小割啊。。。。。

然后構圖的方式就是把作物值分成AB集合，一個在st一邊，一個在ed一邊，st連作物流量為a[i],作物流ed流量為b[i]，對于每一個組合，新建兩個點，一個被st流流量為c1，一個流ed流量為c2，然后第一個流去集合中的作物，作物流回第二個點，流量無限。

sum-最小割

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std;int n,sum,st,ed;struct node {int x,y,c,next,other; }a[2100000];int len,last[110000]; void ins(int x,int y,int c) {int k1,k2;len++;k1=len;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;len++;k2=len;a[len].x=y;a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len;a[k1].other=k2;a[k2].other=k1; } void composition() {int x;sum=0;st=4001,ed=4002;len=0;memset(last,0,sizeof(last));for(int i=1;i<=n;i++)scanf("%d",&x), ins(st,i,x), sum+=x;for(int i=1;i<=n;i++)scanf("%d",&x), ins(i,ed,x), sum+=x;int m,c1,c2;scanf("%d",&m);for(int i=1;i<=m;i++){int t;int chst=n+i,ched=n*2+i;scanf("%d%d%d",&t,&c1,&c2);ins(st,chst,c1);sum+=c1;ins(ched,ed,c2);sum+=c2;for(int j=1;j<=t;j++)scanf("%d",&x), ins(chst,x,999999999), ins(x,ched,999999999);} }//------composition--------int h[110000],list[110000]; bool bt_h() {memset(h,0,sizeof(h));h[st]=1;list[1]=st;int head=1,tail=2;while(head!=tail){int x=list[head];for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(a[k].c>0&&h[y]==0){h[y]=h[x]+1;list[tail]=y;tail++;}}head++;}if(h[ed]>0)return true;return false; } int findflow(int x,int f) {if(x==ed)return f;int s=0;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(a[k].c>0&&h[y]==(h[x]+1)&&s<f){int t=findflow(y,min(a[k].c,f-s));s+=t;a[k].c-=t;a[a[k].other].c+=t;}}if(s==0)h[x]=0;return s; }//---------網絡流---------- int main() {scanf("%d",&n);composition();int ans=0;while(bt_h()==true){ans+=findflow(st,999999999);}printf("%d\n",sum-ans);return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/8343539.html

總結

以上是生活随笔為你收集整理的bzoj3438: 小M的作物的全部內容，希望文章能夠幫你解決所遇到的問題。

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