1070: [SCOI2007]修车
题目:传送门
题解:
一道挺简单的费用流吧...胡乱建模走起
贴个代码...
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,st,ed,ans;
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 head,tail,list[],dis[],pre[],cc[];
bool v[];
bool spfa()
{
memset(cc,,sizeof(cc));cc[st]=;
memset(v,false,sizeof(v));v[st]=true;
memset(dis,0x3F,sizeof(dis));dis[st]=;
head=;tail=;list[]=st;pre[st]=;
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>) && (dis[y]>dis[x]+a[k].d) )
{
cc[y]= min(cc[x],a[k].c);
dis[y]=dis[x]+a[k].d;
pre[y]=k;
if(!v[y])
{
v[y]=true;
list[tail++]=y;
if(tail==ed+) tail=;
} }
}
v[x]=false;
head++; if(head==ed+)head=;
}
if(dis[ed]>)return false;
ans+=dis[ed]*cc[ed];
int x=ed;
while(x!=st)
{
int k=pre[x];
a[k].c-=cc[ed];a[a[k].other].c+=cc[ed];
x=a[k].x;
}
return true;
}
int map[][];
int main()
{
scanf("%d%d",&m,&n);
len=;memset(last,,sizeof(last));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&map[i][j]);
}
st=n+m*n+;ed=st+;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
for(int k=;k<=n;k++)
{
ins(i,j*n+k,,map[i][j]*(n-k+));
}
}
}
for(int i=;i<=n;i++)ins(st,i,,);
for(int i=n+;i<=n+n*m;i++)ins(i,ed,,);
ans=;
while(spfa());
printf("%.2lf\n",double(ans)/n);
return ;
}