P3410 拍照
2024-08-27 03:48:26
漂亮小姐姐点击就送:https://www.luogu.org/problemnew/show/P3410
题目描述
小B有n个下属,现小B要带着一些下属让别人拍照。
有m个人,每个人都愿意付给小B一定钱让n个人中的一些人进行合影。如果这一些人没带齐那么就不能拍照,小B也不会得到钱。
注意:带下属不是白带的!!!对于每个下属,如果他带了那么小B需要给他一些钱,保证当他拍照时配合。
请问,小B的净收益最多是多少。
输入输出格式
输入格式:
第1行有2个正整数m和n(0<m,n<=100)。接下来的m行,每行是一个要求拍照的人的有关数据。第一个数是他同意支付该合影的费用;接着是该合影需要的若干下属的编号,以一个0作为行的结束标记。最后一行的n个数是带每个下属的费用。
输出格式:
一个数,表示最大收益。小B可以一个人也不带。
输入输出样例
说明
对于10%的数据每个人都要求让全部n个人合影
对于30%的数据n<=15 m<=15
另有10%的数据答案为0
对于50%的数据n<=40 m<=40
另有10%的数据每个人只愿意拍一个人
对于100%的数据m,n<=100
//源点向合影连边,边权为得到的钱
//合影向人连边,边权为inf,
//把人拆点,边权为带这个人要付的钱,防止加多次
//人向汇点连边,边权为inf
//先把能赚的钱全都加起来,也就是所有拍照的报酬
//然后跑dinic,算出来的是最小的花费
//就是说,如果拍照得到的钱小于带人的钱,跑出来的就是拍照的钱
//如果拍照的钱大于带人的钱,跑出来的就是带人的钱
//这样一减就是利润。 //我也不知道怎么描述,反正图画出来非常清晰 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std; const int N=1e4+;
const int INF=0x7fffffff; int n,m,S,T;
int a,p;
int c[N];
int head[N],num_edge;
struct Edge
{
int v,flow,nxt;
}edge[N<<];
vector<int> vec[N]; inline int read()
{
char c=getchar();int num=,f=;
for(;!isdigit(c);c=getchar())
f=c=='-'?-:f;
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num*f;
} inline void add_edge(int u,int v,int flow)
{
edge[++num_edge].v=v;
edge[num_edge].flow=flow;
edge[num_edge].nxt=head[u];
head[u]=num_edge;
} int dep[N];
inline bool bfs()
{
memset(dep,,sizeof(dep));
queue<int> que;
que.push(S),dep[S]=;
int now,v;
while(!que.empty())
{
now=que.front(),que.pop();
for(int i=head[now];i;i=edge[i].nxt)
{
if(edge[i].flow)
{
v=edge[i].v;
if(!dep[v])
{
dep[v]=dep[now]+;
if(v==T)
return ;
que.push(v);
}
}
}
}
return ;
} int dfs(int now,int flow)
{
if(now==T)
return flow;
int v,outflow=,tmp;
for(int i=head[now];i;i=edge[i].nxt)
{
if(edge[i].flow)
{
v=edge[i].v;
if(dep[v]!=dep[now]+)
continue;
tmp=dfs(v,min(flow,edge[i].flow));
if(tmp)
{
edge[i].flow-=tmp;
edge[i^].flow+=tmp;
outflow+=tmp;
flow-=tmp;
if(!flow)
return outflow;
}
}
}
dep[now]=;
return outflow;
} int Flow;
int main()
{
num_edge=; //教训!!!
m=read(),n=read();
T=m++n<<;
for(int i=;i<=m;++i)
{
while("why")
{
a=read();
if(!a)
break;
vec[i].push_back(a);
}
Flow+=vec[i][];
}
for(int i=;i<=n;++i)
{
a=read();
// sum+=a;
p=i<<;
add_edge(p-,p,a);
add_edge(p,p-,);
add_edge(p,T,INF);
add_edge(T,p,);
}
for(int i=;i<=m;++i)
{
p=i+n<<;
add_edge(S,p,vec[i][]);
add_edge(p,S,);
for(int j=;j<vec[i].size();++j)
{
add_edge(p,vec[i][j]*-,INF);
add_edge(vec[i][j]*-,p,);
}
}
while(bfs())
{
Flow-=dfs(S,INF);
}
if(Flow<=)
printf("");
else
printf("%d",Flow);
return ;
}
最新文章
- html学习第二天—— 第九、十章——CSS的继承、层叠和特殊性+CSS格式化排版
- jQuery的.bind()、.live()和.delegate()的区别
- 作弊Q-百威
- 数据库(表)的逻辑备份与恢复<;四>;
- Myeclipse:No projects are available for deployment to this server!
- 如风一样,飞翔------Day37
- MySql存储过程的使用
- obj-c编程09:块的语法
- mybatis提示Invalid bound statement (not found)错误的可能原因
- UPX脱壳全程分析(转)
- Edge 浏览器 调用
- grep语法2
- 团队作业Beta冲刺-第三天
- 740. Delete and Earn
- wpf后台设置颜色(背景色,前景色)
- 支撑大规模公有云的Kubernetes改进与优化 (3)
- 网页尺寸offsetHeight,offsetWidth
- Mysql内置功能《一》流程控制
- C#操作Redis SortedSet 有序集合
- 解决java在对MySQL插入数据时出现乱码问题