題目

Feather的農場里有N*M塊地，排列成N行，每行M塊地。Feather在每塊地里種植了不同的農作物。現在這些農作物都成熟了，可以摘取下來出售了。其中第i行第j列的地里的農作物的價值為W[i,j]。
JackRabbit是Feather的好友，平時經常為Feather的農作物除草除蟲。為了答謝JackRabbit，Feather決定把一部分農作物送給JackRabbit。JackRabbit很高興，恨不得一下子把農場里的農作物摘空。
為了防止JackRabbit把農作物摘空，Feather提出了兩個條件：
1.每行最多選取兩塊地；
2.每列最多選取兩塊地。
這下子把JackRabbit難住了。如何在滿足這兩個條件的前提下，使得摘取的農作物的價值之和最大呢？

分析

費用流的模型題，
先考慮構圖，

對于每一行，用一個點表示，因為每行最多選兩塊地，所以從源點s向這n個行點連一條容量為2，費用為0的邊。
對于每一列，同樣用一個點表示，因為每列最多選兩塊地，所以從這m個列點向匯點t連一條容量為2，費用為0的邊。
最后，因為在同一行、同一列最多只有一塊的，所以，從n個行點向m個列點連一條容量為1，費用為W[i,j]的邊。
做一遍費用流就可以了。

#include <cmath> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> const int maxlongint=2147483647; const int mo=1000000007; const int N=50005; using namespace std; int f[400][400],cost[400][400],next[5000],dis[5000],d[1000000],n,m,ans; bool v[5000]; bool spfa() {for(int i=0;i<=n+m+1;i++)dis[i]=-maxlongint;memset(next,0,sizeof(next));memset(v,true,sizeof(v));int head=0,tail=1,k;dis[0]=0;d[0]=0;while(head<tail){k=d[++head];v[k]=true;for(int i=0;i<=n+m+1;i++){if(f[k][i] && dis[i]<dis[k]+cost[k][i]){dis[i]=dis[k]+cost[k][i];next[i]=k;if(v[i]){d[++tail]=i;v[i]=false;}}}}if(dis[n+m+1]<=0) return false;else return true; } int solve() {int sum=maxlongint;for(int i=n+m+1;i;i=next[i]){sum=min(sum,f[next[i]][i]);}for(int i=n+m+1;i;i=next[i]){f[next[i]][i]-=sum;f[i][next[i]]+=sum;ans+=cost[next[i]][i]*sum;} } int main() {freopen("pick.in","r",stdin);freopen("pick.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) f[0][i]=2;for(int i=1;i<=m;i++) f[n+i][n+m+1]=2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&cost[i][n+j]);f[i][n+j]=1;cost[i][n+j]=cost[i][n+j];cost[n+j][i]=-cost[i][n+j];}}ans=0;while(spfa()) solve();printf("%d",ans); }

轉載于:https://www.cnblogs.com/chen1352/p/9013508.html

總結

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

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