1070: [SCOI2007]修车
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3624 Solved: 1452
[Submit][Status][Discuss]
Description
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
Input
第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。
Output
最小平均等待时间，答案精确到小数点后2位。
Sample Input
2 2
3 2
1 4
Sample Output
1.50
HINT
数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)
Source
这个题啊，开始看出来是最小费用最大流了，但不知道怎么建图，人傻的不行，于是第一遍尝试WA告终
借鉴了一下黄学长的建图姿势：
把每个工人拆成N个点，一共N*M个点
超级源S连这N*M个点，容量为1，费用为0
超级汇T连N*M+（1~M）个点（车），容量为1，费用为0
把每个车都与每个拆成的点相连，容量为1，费用为t【k】【i】*j
很显然，每个工人同一时间只能洗一辆车，也只有一辆车能被洗，所以容量为0，至于费用，考虑第i个工人，他修第j辆车只对后面要修的车有影响，而前面修过的车已经对当前没有影响了。而这个影响就是后面每个将要修理的车都多等待了time的时间。
然后zkw一遍除以人数即可。
code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x7fffffff
int n,m;
int pg[100][10];
int S,T;
struct data{
int v,c,to,next;
}edge[500010];
int head[500010],cnt=1;
int h,t,q[500010];
int dis[500010];
bool mark[500010],visit[500010];
int ans;
int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void add(int u,int v,int cap,int cost)
{
cnt++;edge[cnt].v=cap;
edge[cnt].to=v;edge[cnt].c=cost;
edge[cnt].next=head[u];head[u]=cnt;
}
void insert(int u,int v,int cap,int cost)
{
add(u,v,cap,cost);add(v,u,0,-cost);
}
void init()
{
n=read();m=read();
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
pg[i][j]=read();
}
void make()
{
S=0,T=n*m+m+1;
for (int i=1; i<=n*m; i++)
insert(S,i,1,0);
for (int i=n*m+1; i<=n*m+m; i++)
insert(i,T,1,0);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
for (int k=1; k<=m; k++)
insert((i-1)*m+j,n*m+k,1,pg[k][i]*j);
}
bool spfa()
{
memset(visit,false,sizeof(visit));
for (int i=S; i<=T; i++) dis[i]=inf;
h=0,t=1;
q[0]=T;visit[T]=1;dis[T]=0;
while (h<t)
{
int now=q[h];h++;visit[now]=0;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i^1].v && dis[now]-edge[i].c<dis[edge[i].to])
{
dis[edge[i].to]=dis[now]-edge[i].c;
if (!visit[edge[i].to])
{
visit[edge[i].to]=1;
q[t++]=edge[i].to;
}
}
}
return dis[0]!=inf;
}
int dfs(int loc,int low)
{
mark[loc]=true;
if (loc==T) return low;
int w,used=0;
for (int i=head[loc]; i; i=edge[i].next)
if (dis[edge[i].to]==dis[loc]-edge[i].c && edge[i].v && !mark[edge[i].to])
{
w=dfs(edge[i].to,min(low-used,edge[i].v));
ans+=w*edge[i].c;
edge[i].v-=w;edge[i^1].v+=w;
used+=w;if (used==low) return low;
}
return used;
}
void zkw()
{
int tmp=0;
while (spfa())
{
mark[T]=1;
while (mark[T])
{
memset(mark,0,sizeof(mark));
tmp+=dfs(0,inf);
}
}
}
int main()
{
init();
make();
zkw();
printf("%.2f\n",(double)ans/m);
return 0;
}感谢DCrusher神犇，全程观赏水题过程。