图论（网络流）：SCOI 2007 修车

　　同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。

　　说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

输入

　　第一行有两个数M,N，表示技术人员数与顾客数。

　　接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。

输出

　　最小平均等待时间，答案精确到小数点后2位。

样例

repair.in

2 2

3 2

1 4

repair.out

1.50

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

　　网上的题解好多都特别粗略，我走了好多弯路。

　　所以决定写详细一点：把每个修理工变为N个点，表示倒数第1~N个修理的车，为啥是倒数呢？因为不知道一个人究竟修了几辆车，又因为倒数第一的总比倒数第二的更优，费用流会优先倒数第一的，再倒数第二的，所以用倒数的可以很好地解决。多么的巧妙！！！然后是这样建图的：S向每个人的每个倒数第几维修的点连一条流量为1，费用为0的边;接着再新建N个点，代表N辆车,每个人的每个倒数第几维修的点向其连一条流量为1，费用为（当前是倒数第i个的i）*（第j个人修第k辆车的时间）；最后由N辆车的向T连容量为1，费用为0的边。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 const int INF=;

 const int maxn=,maxm=;

 int cnt=,fir[maxn],nxt[maxm],to[maxm];

 int cap[maxm],val[maxm],dis[maxn],path[maxn];

 void add(int a,int b,int c,int v){

     nxt[++cnt]=fir[a];to[cnt]=b;

     cap[cnt]=c;val[cnt]=v;fir[a]=cnt;

 }

 void addedge(int a,int b,int c,int v){

     add(a,b,c,v);

     add(b,a,,-v);

 }

 int S,T;

 int vis[maxn];

 int Spfa(){

     deque<int>q;

     memset(dis,,sizeof(dis));

     memset(vis,,sizeof(vis));

     q.push_front(S);

     dis[S]=;vis[S]=;

     while(!q.empty()){

         int x=q.front();q.pop_front();vis[x]=;

         for(int i=fir[x];i;i=nxt[i])

             if(cap[i]&&dis[x]+val[i]<dis[to[i]]){

                 dis[to[i]]=val[i]+dis[x];

                 path[to[i]]=i;

                 if(vis[to[i]])continue;

                 if(dis[to[i]]<dis[x])

                     q.push_front(to[i]);

                 else

                     q.push_back(to[i]);

                 vis[to[i]]=;

             }

     }

     return dis[T]==dis[T+]?:dis[T];

 }

 int Aug(){

     int p=T,f=INF;

     while(p!=S){

         f=min(f,cap[path[p]]);

         p=to[path[p]^];

     }

     p=T;

     while(p!=S){

         cap[path[p]]-=f;

         cap[path[p]^]+=f;

         p=to[path[p]^];

     }

     return f;

 }

 int MCMF(){

     int ret=,d;

     while(d=Spfa())

         ret+=Aug()*d;

     return ret;

 }

 int n,m;

 int a[maxn][maxn];

 int main(){

     freopen("scoi2007_repair.in","r",stdin);

     freopen("scoi2007_repair.out","w",stdout);

     scanf("%d%d",&m,&n);

     S=;T=n*m+n+;

     for(int i=;i<=n;i++){

         addedge(n*m+i,T,,);

         for(int j=;j<=m;j++)

             addedge(S,(i-)*m+j,,);

     }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             scanf("%d",&a[i][j]);

     for(int j=;j<=m;j++)

         for(int i=;i<=n;i++)

             for(int k=;k<=n;k++)

                 addedge((i-)*m+j,n*m+k,,i*a[k][j]);

     printf("%.2f\n",1.0*MCMF()/n);

     return ;

 }