TYVJ1982 武器分配

描述

    后勤部队运来一批武器（机枪和盔甲）。你要把这些武器分配给手下的marine们（每人一部机枪，一套盔甲）。可是问题来了。。。
    这些武器的型号不相同（武器是由出价最低的承包商制造的），把一部m型的机枪和一套n型的盔甲分配给一个marine得到的不满意值为(m-n)^2（每个marine当然希望自己得到的武器是同一型号的）。
    你的任务就是把a部机枪和b套盔甲分配给手下n个marine。使他们的不满意值之和最小。

输入格式

第一行：3 个正整数 n , a , b (1<=n<=a,b<=80)
第二行：a 个数表示每部机枪的型号
第三行：b 个数表示每套盔甲的型号
0<=型号值<=10000

输出格式

输出一个数：最小不满意值。

测试样例1

输入

输出

费用流。

有最大流量限制，那么就在汇点T后面加个T2，从T到T2连边，容量为n(最大人数)。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<cstring>

 using namespace std;

 const int INF=1e8;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct edge{

     int from,v,nxt;

     int f,w;

 }e[mxn<<];

 int hd[mxn],mct=;//

 inline void add_edge(int u,int v,int c,int w){

     e[++mct].v=v;e[mct].from=u;e[mct].nxt=hd[u];e[mct].f=c;e[mct].w=w;hd[u]=mct;return;

 }

 void insert(int u,int v,int c,int w){

     add_edge(u,v,c,w);

     add_edge(v,u,,-w);

     return;

 }

 //

 int n,m;

 int S,T,T2;

 int ans=;

 //

 int dis[mxn];

 bool inq[mxn];

 int pre[mxn<<];

 void SPFA(int s){

     memset(dis,0x3f,sizeof dis);

     memset(pre,-,sizeof pre);

     queue<int>q;

     dis[s]=;

     inq[s]=;

     q.push(s);

     while(!q.empty()){

         int u=q.front();q.pop();inq[u]=;

         for(int i=hd[u];i;i=e[i].nxt){

             if(!e[i].f)continue;

             int v=e[i].v;

             if(dis[v]>dis[u]+e[i].w){

                 dis[v]=dis[u]+e[i].w;

                 pre[v]=i;//记录前驱边

                 if(!inq[v]){

                     inq[v]=;

                     q.push(v);

                 }

             }

         }

     }

     return;

 }

 void maxflow(int s,int t){

     SPFA(s);

     while(pre[t]!=-){

         int tmp=INF;

         for(int i=pre[t];i!=-;i=pre[e[i].from])

             tmp=min(tmp,e[i].f);

         ans+=dis[t]*tmp;

         for(int i=pre[t];i!=-;i=pre[e[i].from]){

             e[i].f-=tmp;

             e[i^].f+=tmp;

         }

         SPFA(s);

     }

     return;

 }

 int a,b;

 int ac[],bc[];

 int main()

 {

     int i,j,u,v;

     n=read();a=read();b=read();

     for(i=;i<=a;i++){ac[i]=read();}

     for(i=;i<=b;i++){bc[i]=read();}

     S=;T=a+b+;T2=T+;

     for(i=;i<=a;i++)

         for(j=;j<=b;j++){

             insert(i,a+j,,(ac[i]-bc[j])*(ac[i]-bc[j]));

         }

     for(i=;i<=a;i++)insert(S,i,,);

     for(i=;i<=b;i++)insert(a+i,T,,);

     insert(T,T2,n,);//限制匹配人数

     maxflow(S,T2);

     printf("%d\n",ans);

     return ;

 }