2039: [2009国家集训队]employ人员雇佣
Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 1511 Solved: 728Description
作为一个富有经营头脑的富翁,小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,(我们用Ei,j表示i经理对j经理的了解程度),即当经理i和经理j同时被雇佣时,经理i会对经理j做出贡献,使得所赚得的利润增加Ei,j。当然,雇佣每一个经理都需要花费一定的金钱Ai,对于一些经理可能他做出的贡献不值得他的花费,那么作为一个聪明的人,小L当然不会雇佣他。 然而,那些没有被雇佣的人会被竞争对手所雇佣,这个时候那些人会对你雇佣的经理的工作造成影响,使得所赚得的利润减少Ei,j(注意:这里的Ei,j与上面的Ei,j 是同一个)。 作为一个效率优先的人,小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗?
Input
第一行有一个整数N<=1000表示经理的个数 第二行有N个整数Ai表示雇佣每个经理需要花费的金钱 接下来的N行中一行包含N个数,表示Ei,j,即经理i对经理j的了解程度。(输入满足Ei,j=Ej,i)
Output
第一行包含一个整数,即所求出的最大值。
Sample Input
3
3 5 100
0 6 1
6 0 2
1 2 0Sample Output
1
【数据规模和约定】
20%的数据中N<=10
50%的数据中N<=100
100%的数据中 N<=1000, Ei,j<=maxlongint, Ai<=maxlongintHINT
Source
【分析】
海陆型构图。//到时候再总结这个吧
S集表示雇佣,T集表示不雇佣。每个经理拆成x,y两点。s向所有x点连,流量为雇佣费用。对于每个Ei,j,i,j经理连一条流量为2*Ei,j的无向边,同时i和j都向t连流量为Ei,j的边,最小割为所有Ei,j*2减最大流。由于边数大,需要合并一下边。
【啊一开始构错图了,好桑心。。。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1100
#define INF 0xfffffff int mymin(int x,int y) {return x<y?x:y;} int a[Maxn],w[Maxn][Maxn]; struct node
{
int x,y,f,next,o;
}t[Maxn*Maxn*];
int len,first[Maxn]; void ins(int x,int y,int f)
{
t[++len].x=x;t[len].y=y;t[len].f=f;
t[len].next=first[x];first[x]=len;t[len].o=len+;
t[++len].x=y;t[len].y=x;t[len].f=;
t[len].next=first[y];first[y]=len;t[len].o=len-;
} int st,ed;
int dis[Maxn];
queue<int > q;
bool bfs()
{
for(int i=;i<=ed;i++) dis[i]=-;
while(!q.empty()) q.pop();
dis[st]=;q.push(st);
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==-)
{
dis[y]=dis[x]+;
q.push(y);
}
}
q.pop();
}
if(dis[ed]==-) return ;
return ;
} int ffind(int x,int flow)
{
if(x==ed) return flow;
int now=;
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==dis[x]+)
{
int a=ffind(y,mymin(flow-now,t[i].f));
t[i].f-=a;
t[t[i].o].f+=a;
now+=a;
}
if(now==flow) break;
}
if(now==) dis[x]=-;
return now;
} void output()
{
for(int i=;i<=len;i+=)
{
printf("%d -> %d %d\n",t[i].x,t[i].y,t[i].f);
}printf("\n");
} int ans;
void max_flow()
{
while(bfs())
{
ans-=ffind(st,INF);
// output();
// while(1);
}
} int s[Maxn]; int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
ans=;
for(int i=;i<=n;i++)
{
s[i]=;
for(int j=;j<=n;j++)
{
scanf("%d",&w[i][j]);
s[i]+=w[i][j];
ans+=w[i][j];
}
} len=;
memset(first,,sizeof(first));
st=n+;ed=st+;
for(int i=;i<=n;i++) ins(st,i,a[i]);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++) {ins(i,j,*w[i][j]);ins(j,i,*w[i][j]);}
for(int i=;i<=n;i++) ins(i,ed,s[i]);
// output();
max_flow();
printf("%d\n",ans);
return ;
}
2017-03-28 20:58:42