首页 > 代码库 > TYVJ1982 武器分配

TYVJ1982 武器分配

2024-08-28 09:41:19   218人阅读

描述

    后勤部队运来一批武器（机枪和盔甲）。你要把这些武器分配给手下的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

输入

Sample 1：
2 3 3
9 10 20
0 10 11
Sample 2：
3 4 4
3 9 7 4
4 2 5 5

输出

Sample 1：
2
Sample 2：
5

 

费用流。

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

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<queue> 6 #include<cstring> 7 using namespace std; 8 const int INF=1e8; 9 const int mxn=9000;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 struct edge{17     int from,v,nxt;18     int f,w;19 }e[mxn<<1];20 int hd[mxn],mct=1;//21 inline void add_edge(int u,int v,int c,int w){22     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;23 }24 void insert(int u,int v,int c,int w){25     add_edge(u,v,c,w);26     add_edge(v,u,0,-w);27     return;28 }29 //30 int n,m;31 int S,T,T2;32 int ans=0;33 //34 int dis[mxn];35 bool inq[mxn];36 int pre[mxn<<1];37 void SPFA(int s){38     memset(dis,0x3f,sizeof dis);39     memset(pre,-1,sizeof pre);40     queue<int>q;41     dis[s]=0;42     inq[s]=1;43     q.push(s);44     while(!q.empty()){45         int u=q.front();q.pop();inq[u]=0;46         for(int i=hd[u];i;i=e[i].nxt){47             if(!e[i].f)continue;48             int v=e[i].v;49             if(dis[v]>dis[u]+e[i].w){50                 dis[v]=dis[u]+e[i].w;51                 pre[v]=i;//记录前驱边 52                 if(!inq[v]){53                     inq[v]=1;54                     q.push(v);55                 }56             }57         }58     }59     return;60 }61 void maxflow(int s,int t){62     SPFA(s);63     while(pre[t]!=-1){64         int tmp=INF;65         for(int i=pre[t];i!=-1;i=pre[e[i].from])66             tmp=min(tmp,e[i].f);67         ans+=dis[t]*tmp;68         for(int i=pre[t];i!=-1;i=pre[e[i].from]){69             e[i].f-=tmp;70             e[i^1].f+=tmp;71         }72         SPFA(s);73     }74     return;75 }76 int a,b;77 int ac[120],bc[120];78 int main()79 {80     int i,j,u,v;81     n=read();a=read();b=read();82     for(i=1;i<=a;i++){ac[i]=read();}83     for(i=1;i<=b;i++){bc[i]=read();}84     S=0;T=a+b+1;T2=T+1;85     for(i=1;i<=a;i++)86         for(j=1;j<=b;j++){87             insert(i,a+j,1,(ac[i]-bc[j])*(ac[i]-bc[j]));88         }89     for(i=1;i<=a;i++)insert(S,i,1,0);90     for(i=1;i<=b;i++)insert(a+i,T,1,0);91     insert(T,T2,n,0);//限制匹配人数 92     maxflow(S,T2);93     printf("%d\n",ans);94     return 0;95 }

 

TYVJ1982 武器分配


联系
我们