bzoj 1070 [SCOI2007]修车——网络流(拆边)

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1070

后面还有几辆车在这个人这儿修,自己这辆车的时间对总时间的贡献就要多乘上几倍。

所以可以费用流。每辆车向每个人连 n 条边,费用依次为 d , 2*d , 3*d …… 表示自己后面有几辆车。

对于一个人来说,还要限制走 k*d 这条边的一共只能有一辆车。只需要将一个人拆成 n 个点,每个点向汇点连容量为1的边就行了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mn(int a,int b){return a<b?a:b;}
const int N=,M=,INF=;
int n,m,t,hd[N],xnt=,cur[N],to[M],nxt[M],cap[M],w[M];
int dis[N],pre[N],info[N],ans; bool ins[N];
queue<int> q;
void add(int x,int y,int z)
{
to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;cap[xnt]=;w[xnt]=z;
to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;cap[xnt]=;w[xnt]=-z;
}
bool spfa()
{
memset(dis,0x3f,sizeof dis);dis[]=;
info[]=INF;info[t]=;
q.push();ins[]=;
while(q.size())
{
int k=q.front();q.pop();ins[k]=;
for(int i=hd[k],v;i;i=nxt[i])
if(cap[i]&&dis[v=to[i]]>dis[k]+w[i])
{
dis[v]=dis[k]+w[i];
pre[v]=i; info[v]=Mn(info[k],cap[i]);
if(!ins[v])q.push(v),ins[v]=;
}
}
return info[t];
}
void ek()
{
int s=info[t];
for(int i=pre[t];i;i=pre[to[i^]])
{
ans+=s*w[i];cap[i]-=s;cap[i^]+=s;
}
}
int main()
{
scanf("%d%d",&m,&n);int ct=n*m; t=ct+n+;
for(int i=,x=ct+,d;i<=n;i++,x++)
for(int j=,y=;j<=m;j++,y++)
{
d=rdn();
for(int k=,lj=d;k<=n;k++,lj+=d,y++)
add(x,y,lj);
}
for(int i=,x=ct+;i<=n;i++,x++)add(,x,);
for(int i=;i<=ct;i++)add(i,t,);
while(spfa())ek();
printf("%.2f\n",(double)ans/n);
return ;
}
上一篇:BZOJ 1070: [SCOI2007]修车 [最小费用最大流]


下一篇:MVC4多语言IHttpModule实现