题目描述 Description
假设以最美观的方式布置花店的橱窗，有F束花，V个花瓶，我们用美学值（一个整数）表示每束花放入每个花瓶所产生的美学效果。为了取得最佳的美学效果，必须使花的摆放取得最大的美学值。
第一行为两个整数F,V(F<=V<=100)
接下来F行每行V个整数，第i行第j个数表示第i束花放入第j个花瓶的美学值。
输出描述 Output Description
一个整数，即最大美学值。
2 2
10 0
5 2
样例输出 Sample Output
12
一道挺裸的题目吧
跑了费用流，然后单路增广
em.......
数据中有负权边
所以注意spfa前dis数组初始化为-inf（为了这个调了很久TAT）
然后建边之后一定要调试！一定要调试！一定要调试！（重要的事说三遍）
看你建的边对不对
要不等你整个码完了很难发现是哪里错了
还有const 的int 要注意区分，不小心弄错了又调了很久
最后，反向弧要开两倍！！！
#include<cstdio>
#include<cstring>
const int M=103*103*2,N=210,len=10000;
struct node
{
int from,to,next,v,c;
}e[M];
int first[N];
int s=0,t;
int dis[N],bo[N],qu[len];
int from[N];
int ans=0;
bool spfa()
{
for(int i=1;i<=t;i++) dis[i]=1e8*-1;
dis[0]=0;
bo[0]=1;
qu[1]=0;
int i=1,j=2;
while(i!=j)
{
int r=qu[i++];if(i==len) i=1;bo[r]=0;
for(int k=first[r];k;k=e[k].next)
{
if(e[k].v>0&&dis[e[k].to]<dis[r]+e[k].c)
{
dis[e[k].to]=dis[r]+e[k].c;
from[e[k].to]=k;
if(!bo[e[k].to])
{
if(dis[e[k].to]>dis[qu[i]])
{
i--;if(i<1) i=len-1;
qu[i]=e[k].to;
}
else
{
qu[j++]=e[k].to;if(j==len) j=1;
}
bo[e[k].to]=1;
}
}
}
}
if(dis[t]<0) return 0;
return 1;
}
void fa()
{
int min=1e8;
for(int k=from[t];k;k=from[e[k].from])
min=min<e[k].v?min:e[k].v;
for(int k=from[t];k;k=from[e[k].from])
{
e[k].v-=min;e[k^1].v+=min;
ans+=e[k].c*min;
}
}
int main()
{
int f,n,cnt=1;
scanf("%d %d",&f,&n);
t=f+n+1;
int k;
for(int i=1;i<=f;i++)
{//没有写成函数，略丑TAT
e[++cnt].to=i;e[cnt].from=s;e[cnt].v=1;e[cnt].c=0;e[cnt].next=first[s];first[s]=cnt;
e[++cnt].to=s;e[cnt].from=i;e[cnt].v=0;e[cnt].c=0;e[cnt].next=first[i];first[i]=cnt;
for(int j=1;j<=n;j++)
{
scanf("%d",&k);
e[++cnt].to=f+j;e[cnt].v=1;e[cnt].from=i;e[cnt].c=k;e[cnt].next=first[i];first[i]=cnt;
e[++cnt].to=i;e[cnt].v=0;e[cnt].from=f+j;e[cnt].c=-k;e[cnt].next=first[f+j];first[f+j]=cnt;
if(i==1)
{
e[++cnt].to=t;e[cnt].from=f+j;e[cnt].v=1;e[cnt].c=0;e[cnt].next=first[f+j];first[f+j]=cnt;
e[++cnt].to=f+j;e[cnt].from=t;e[cnt].v=0;e[cnt].c=0;e[cnt].next=first[t];first[t]=cnt;
}
}
}
while(spfa()) fa();
printf("%d",ans);
return 0;
}
