[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();
}

加入对话

1条评论

留下评论

您的电子邮箱地址不会被公开。