3442: 学习小组
题目：传送门
题解：
超级好题啊大佬们的神题！建图肥肠灵性！感觉自己是星际玩家。。。
首先呢st直接向每个人连边，容量为min(k,喜欢的小组个数)，费用为0
然后每个人再向ed连，因为题目要求人数尽量多，那么每个人都至少要去一个学习小组，那么容量就为min(k-1,喜欢的小组个数-1)，费用为0（表示每个人最多能不选的小组）
每个人还要向自己喜欢的小组连边，容量为1，费用就为-F[i]（因为题目问的是最小的支出，那么F表示的是手续费，所以肯定为负）
灵性的操作来了：
每个小组当然是还要向ed连的。
直接就把每个小组向ed连n条边，表示不同人数参加该小组时的花费
容量为1，流量就要推导一下：
对于有i-1个人参加了该小组j，那么多一个人的费用差就是：C[j]*i^2-C[j]*(i-1)^2
化简之后就是：C[j]*(2*i-1);
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 999999999
using namespace std;
struct node
{
int x,y,c,d,next,other;
}a[];int len,last[];
void ins(int x,int y,int c,int d)
{
int k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=;a[len].d=-d;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int list[],d[],la[],head,tail,st,ed,n,m,k,ans;
bool v[];
bool spfa()
{
for(int i=;i<=ed;i++)d[i]=inf;
memset(v,false,sizeof(v));memset(la,,sizeof(la));
list[]=st;d[st]=;v[st]=true;head=;tail=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k].c> && d[y]>d[x]+a[k].d)
{
d[y]=d[x]+a[k].d;la[y]=k;
if(v[y]==false)
{
v[y]=true;
list[tail++]=y;
if(tail==ed+)tail=;
}
}
}
head++;if(head==ed+)head=;
v[x]=false;
}
if(d[ed]==inf)return false;
return true;
}
int g_f()
{
int x,k,ans=,f=inf;
x=ed;while(x!=st){k=la[x];f=min(f,a[k].c);x=a[k].x;}
x=ed;while(x!=st){k=la[x];a[k].c-=f;a[a[k].other].c+=f;x=a[k].x;}
ans+=d[ed]*f;
return ans;
}
int C[],F[],tot[];
char s[];
int main()
{
scanf("%d%d%d",&n,&m,&k);len=;memset(last,,sizeof(last));st=n+m+,ed=st+;
for(int i=;i<=m;i++)scanf("%d",&C[i]);for(int i=;i<=m;i++)scanf("%d",&F[i]);
for(int i=;i<=n;i++)
{
scanf("%s",s+);
for(int j=;j<=m;j++)if(s[j]=='')ins(i,j+n,,-F[j]),tot[i]++;
}
for(int i=;i<=n;i++)ins(st,i,min(k,tot[i]),),ins(i,ed,min(k-,tot[i]-),);
//C[j]*i^2-C[j]*(i-1)^2-->C[j]*(2*i-1)
for(int j=;j<=m;j++)for(int i=;i<=n;i++)ins(j+n,ed,,C[j]*(*i-));
ans=;while(spfa())ans+=g_f();printf("%d\n",ans);
return ;
}