分类存档：默认分类

【题目】

提交文件：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();
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1532
【算法分析】
二分答案然后，将比赛分配给选手，判定能不能分完。
这个用最大流实现。
【其它】sap被卡。HLPP被卡。。。于是dinic。。。
于是你可以见识到什么叫卡过。。。
34 30276 edward_mj 3164K 4772MS G++ 2.39K 2010-06-16 01:39:26 【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
const int N=20005;
const int INF=0x7FFFFFFF;
struct edge{int x,y,c;edge *next,*op;}*ls[N],*cur[N],*fa[N];
int n,m,vs,vt,Flow;
int d[N],lx[N],ly[N],v[N],Q[N];

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&lx[i],&ly[i]);
vs=0; vt=n+m+1;
}

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

bool bfs(){
for (int i=vs;i<=vt;i++){
d[i]=INF;
v[i]=0;
cur[i]=ls[i];
}
d[vs]=1; Q[1]=vs;
for (int st=1,ed=1;st<=ed;st++)
for (edge *t=ls[Q[st]];t;t=t->next)
if (t->c && d[t->y]==INF){
d[t->y]=d[t->x]+1;
Q[++ed]=t->y;
if (t->y==vt) return true;
}
return false;
}

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

void dinic(){
int i;
while (bfs()){
i=vs;
while (cur[vs]){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->x]+1==d[t->y] && !v[t->y]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==vt){
change();
i=vs;
}
}else{
v[i]=1;
if (i!=vs) i=fa[i]->x;
}
}
}
}

bool Can(int Limit){
for (int i=vs;i<=vt;i++)
while (ls[i]){
edge*t=ls[i];
ls[i]=t->next;
free(t);
}
for (int i=1;i<=m;i++){
addedge(vs,i,1);
addedge(i,m+lx[i],1);
addedge(i,m+ly[i],1);
}
for (int i=1;i<=n;i++) addedge(m+i,vt,Limit);
Flow=0;
dinic();
if (Flow==m) return true;
return false;
}

void solve(){
int l=m/n,r=m,mid;
while (l mid=(l+r)/2;
if (Can(mid)) r=mid;
else l=mid+1;
}
printf("%dn",l);
}

int main(){
init();
solve();
}