[GD_SGOI 摘取作物]费用流

【题目】

提交文件：pick.pas/.cpp

输入文件：pick.in

输出文件：pick.out

 

Feather的农场里有N*M块地，排列成N行，每行M块地。Feather在每块地里种植了不同的农作物。现在这些农作物都成熟了，可以摘取下来出售了。其中第i行第j列的地里的农作物的价值为W[i,j]。

JackRabbit是Feather的好友，平时经常为Feather的农作物除草除虫。为了答谢JackRabbit，Feather决定把一部分农作物送给JackRabbit。JackRabbit很高兴，恨不得一下子把农场里的农作物摘空。

为了防止JackRabbit把农作物摘空，Feather提出了两个条件：

1.每行最多选取两块地；

2.每列最多选取两块地。

　　这下子把JackRabbit难住了。如何在满足这两个条件的前提下，使得摘取的农作物的价值之和最大呢？

 

输入格式：

　　第一行是两个整数Ｎ和Ｍ（3≤N≤30，3≤M≤30）。

　　以下N行每行M个整数，表示每块地的农作物的价值W[i,j]（0≤W[i,j]≤10000）。

 

输出格式：

　　输出一个数，表示在满足条件的前提下摘取的农作物的价值之和的最大值。

 

输入样例:

3 3

1 5 3

4 7 5

0 4 1

 

输出样例：

21

 

样例解释：

第一行选5和3，第二行选4和5，第三行选0和4，总和为21，是满足条件的最佳选取方案。

【算法分析】
本题是这套题里最脑残的题目。
就是二分图。左边的点是行，右边的点是列。
中间连容量为1，费用为a[i][j]的边。
左右两边与源汇连容量为2的边。
但是直接这样求最大费用最大流是会错误的。
为什么呢？
因为最大流不一定取得最大费用。
最大费用最大流是保证流量最大的情况下取得的费用最大。
于是我们需要将二分图左边的点都向汇连容量为2的边。这要可以允许“不选满”。
然后最后的流量必定是2*n （n是二分图左边的点数）。
又能保证费用最大。
【其它】
在交卷之前，我对我可爱的徒弟小肥闽曰：“你第三题不要错了啊~”
肥闽答曰：“第三题错了我自切JJ！”
然后，他果断错了1个点，就是因为没有处理上述那种情况，于是果断SB。要是数据再黑一点果断要挂。。。。
【CODE】
#include #include #include const int N=30005;
const int INF=1000000000;
struct edge{int x,y,c,w;edge *next,*op;}*ls[N],*fa[N];
int m,n,vs,vt,cost;
int d[N],Q[N],v[N];

void addedge(int x,int y,int c,int w){
edge *p=(edge*)malloc(sizeof(edge));
edge *q=(edge*)malloc(sizeof(edge));
p->x=x; p->y=y; p->c=c; p->w= w; p->next=ls[x]; ls[x]=p; p->op=q;
q->x=y; q->y=x; q->c=0; q->w=-w; q->next=ls[y]; ls[y]=q; q->op=p;
}

void init(){
int i,j,x;
scanf("%d%d",&m,&n);
for (i=1;i<=m;i++)
for (j=1;j<=n;j++){
scanf("%d",&x);
addedge(i,m+j,1,x);
}
vs=0; vt=m+n+1;
for (i=1;i<=m;i++){
addedge(vs,i,2,0);
addedge(i,vt,2,0);
}
for (i=1;i<=n;i++) addedge(m+i,vt,2,0);
}

bool spfa(){
int head=0,tail=1;
for (int i=vs;i<=vt;i++){
d[i]=-INF;
v[i]=0;
}
d[vs]=0; v[vs]=1; Q[1]=vs;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[Q[head]];t;t=t->next)
if (t->c && d[t->x]+t->w>d[t->y]){
d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
Q[tail]=t->y;
}
}
v[Q[head]]=0;
}
if (d[vt]<=0) return false;
return true;
}

void change(){
int nf=INF;
for (int i=vt;i!=vs;i=fa[i]->x)
if (fa[i]->c cost+=nf*d[vt];
for (int i=vt;i!=vs;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void MCMF(){
cost=0;
while (spfa()) change();
printf("%dn",cost);
}

int main(){
freopen("pick.in","r",stdin);
freopen("pick.out","w",stdout);
memset(ls,0,sizeof(ls));
init();
MCMF();
}