How to earn more
| My Tags | (Edit) |
|---|
| Source : ww | |||
| Time limit : 1 sec | Memory limit : 64 M | ||
Submitted : 373, Accepted : 212
Xiao Ming is an expert in computer science and technology, so he can get a lot of projects every month. The projects always bring him a lot of money, now he is thinking how toearn money as more as possible.
Every month he can get m projects, and each project Ai will bring him Xiyuan. Although Xiao Ming is an expert, he still needs to hire someother guys to help him. Of course, the employees are not as good as Xiao Ming, for they are just good at some single aspect. So, they should work together to finish one project.There is a list shows the salary of m employees, who are labeled from 0 to m-1. Xiao Ming only hires employees, in that list, and he knows who will be needed by each project.If one employee is hired, he can join in several projects.
Input
The first line is an integer c shows the number of cases. For each case, the first line has two numbersm,n(m,n <=100), denoting that there is m projects and n employees on the list.The second line hasm integers, which are seperated by a single blank, the ith number Ximeans the project Ai will bring Xiao Ming Xiyuan.Xi is less the 10000. The third line has n integers, which are seperated by a single blank,the ith number Yimeans the employee Bi will cost Xiao Ming Yiyuan.And the next m lines will show which part of the employees will be needed by each project. Linei is a list of the employees, who are needed by project Ai.In each line, first a number Zi shows the number of employees needed by this project. And Zi labels of the emloyees follows, which are still seperated by a sigle blank.
Output
You should output a single integer shows the maximun money Xiao Ming can earn in a single month. The money he can earn is equall to the money he can totally get minus the money he totally cost. You should not leave any extra blanks at the end of each line.
Sample Input
1
3 5
30 40 43
55 17 23 22 11
3 0 1 2
3 1 2 3
2 2 1
Sample Output
21
Hint
If Xiao Ming can do less project to earn more money, he will certainly do that.
【题目大意】
有M个项目和N个员工。做项目i可以获得Ai元，但是必须雇用若干个指定的员工。雇用员工j需要花费Bj元，且一旦雇用，员工j可以参加多个项目的开发。问经过合理的项目取舍，最多能挣多少钱。（1 <= M, N <= 100）
【建模方法】
注意到题目中加粗的两个字“必须”，此题是典型的“蕴含式最大获利问题”，套用解决最大权闭合子图的建模方法即可解决。每个项目i作为一个点并连边(s, i, Ai)，每名员工j作为一个点并连边(j, t, Bj)，若项目i需要雇用员工j则连边(i, j, ∞)。设最小割为ans，那么ΣAi-ans即为结果。（引自《网络流建模汇总》by Edelweiss）
总结：图论的题目会wa总是因为数组范围开的不够大。
| 2634 | 2016-07-14 10:52:50 | Accepted | 0.00 s | 3228 K | C++ | 2979 B | ksq2013 |
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int m,n,s,t,ecnt,first[500],nxt[100100],ans,tot;
struct Edge{int u,v,cap,flow;}e[100100];
bool vis[500];
int d[500],p[500],q[500],cur[500],num[500];
void Link(int a,int b,int c)
{
e[++ecnt].u=a,e[ecnt].v=b,e[ecnt].cap=c,e[ecnt].flow=0;
nxt[ecnt]=first[a],first[a]=ecnt;
e[++ecnt].u=b,e[ecnt].v=a,e[ecnt].cap=0,e[ecnt].flow=0;
nxt[ecnt]=first[b],first[b]=ecnt;
}
void bfs()
{
memset(vis,false,sizeof(vis));
int head=0,tail=1;
q[0]=t,d[t]=0,vis[t]=true;
while(head^tail){
int now=q[head++];
for(int i=first[now];i;i=nxt[i])
if(!vis[e[i].u]&&e[i].cap>e[i].flow){
vis[e[i].u]=true;
d[e[i].u]=d[now]+1;
q[tail++]=e[i].u;
}
}
}
int Agument()
{
int x=t,a=INF;
while(x^s){
a=min(a,e[p[x]].cap-e[p[x]].flow);
x=e[p[x]].u;
}
x=t;
while(x^s){
e[p[x]].flow+=a;
e[p[x]^1].flow-=a;
x=e[p[x]].u;
}
return a;
}
int ISAP()
{
int flow=0;
bfs();
memset(num,0,sizeof(num));
for(int i=0;i<=n+m+1;i++)num[d[i]]++;
int x=s;
for(int i=0;i<=n+m+1;i++)cur[i]=first[i];
while(d[s]<n+m+2){
if(!(x^t)){
flow+=Agument();
x=s;
}
bool advanced=false;
for(int i=cur[x];i;i=nxt[i])
if(e[i].cap>e[i].flow&&d[x]==d[e[i].v]+1){
advanced=true;
p[e[i].v]=i;
cur[x]=i;
x=e[i].v;
break;
}
if(!advanced){
int mn=m+n;
for(int i=first[x];i;i=nxt[i])
if(e[i].cap>e[i].flow)
mn=min(mn,d[e[i].v]);
if(--num[d[x]]==0)break;
num[d[x]=mn+1]++;
cur[x]=first[x];
if(x^s)x=e[p[x]].u;
}
}
return flow;
}
int main()
{
int T;
scanf("%d",&T);
for(;T;T--){
scanf("%d%d",&m,&n);
s=0,t=m+n+1,ecnt=1,ans=tot=0;
memset(first,0,sizeof(first));
memset(nxt,0,sizeof(nxt));
memset(d,0,sizeof(d));
memset(q,0,sizeof(q));
memset(p,0,sizeof(p));
for(int i=1;i<=m;i++){
int x;
scanf("%d",&x);
Link(s,i,x);
tot+=x;
}
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
Link(i+m,t,x);
}
for(int i=1;i<=m;i++){
int tmp;
scanf("%d",&tmp);
for(int x;tmp;tmp--){
scanf("%d",&x);
Link(i,x+1+m,INF);
}
}
ans=ISAP();
printf("%d\n",tot-ans);
}
return 0;
}