bzoj 1070 [SCOI2007]修车

最小费用最大流。

将每个技术人员拆成车数个点，技术人员i的第j个点代表技术人员i修的倒数第j辆车。

源点向所有技术人员点连一条容量为1费用为0的边。

所有技术人员点向所有车点连边：技术人员i的第j个点向第k个车点连一条容量为1费用为T[k][i]*j的边。

所有车点向汇点连一条容量为1费用为0的边。

由于每辆车只能被修一次，如果将车拆点则无法保证这一性质，所以考虑将人拆点。因为不知道每个人会修几辆车，于是将点定义为该工人修的倒数第i辆车，这样便能将每个点对之后的影响加在这个点值里。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int dian=;

 const int bian=;

 int h[dian],nxt[bian],ver[bian],val[bian],cos[bian],minn[dian],with[dian];

 int d[dian],v[dian];

 int map[][];

 int n,m,tot;

 int S,T;

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

     tot++;ver[tot]=b;val[tot]=c;cos[tot]=d;nxt[tot]=h[a];h[a]=tot;

     tot++;ver[tot]=a;val[tot]=;cos[tot]=-d;nxt[tot]=h[b];h[b]=tot;

 }

 bool tell(){

     memset(v,,sizeof(v));

     memset(d,0x3f,sizeof(d));

     memset(with,,sizeof(with));

     memset(minn,0x3f,sizeof(minn));

     queue<int>q;

     q.push(S);

     v[S]=;

     d[S]=;

     while(!q.empty()){

         int x=q.front();

         q.pop();

         v[x]=;

         for(int i=h[x];i;i=nxt[i]){

             int y=ver[i];

             if(d[y]>d[x]+cos[i]&&val[i]){

                 d[y]=d[x]+cos[i];

                 minn[y]=min(minn[x],val[i]);

                 with[y]=i;

                 if(!v[y]){

                     v[y]=;

                     q.push(y);

                 }

             }

         }

     }

     if(d[T]==0x3f3f3f3f)

         return ;

     return ;

 }

 int zeng(){

     for(int i=T;i!=S;i=ver[with[i]^]){

         val[with[i]]-=minn[T];

         val[with[i]^]+=minn[T];

     }

     return d[T]*minn[T];

 }

 int dinic_cost(){

     int r=;

     while(tell())

         r+=zeng();

     return r;

 }

 int main(){

     memset(h,,sizeof(h));

     memset(nxt,,sizeof(nxt));

     tot=;

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

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

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

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

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

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

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

             add(S,(i-)*n+j,,);

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

                 add((i-)*n+j,n*m+k,,map[k][i]*j);

         }

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

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

     printf("%.2f",(double)dinic_cost()/n);

     return ;

 }

注意n和m的定义和读入。