题面

题意:n个英雄,m个怪兽,第i个英雄可以打第i个集合里的一个怪兽,一个怪兽可以在多个集合里,有k瓶药水,每个英雄最多喝一次,可以多打一只怪兽,求最多打多少只 n,m,k<=500

题解:显然的最大流裸题,多加一个药水点,药酱入度k,然后再连向英雄

队友抄的模板所以不是我的那个板子

 #include<bits/stdc++.h>
using namespace std;
struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int c,int f)
{
from=u;
to=v;
cap=c;
flow=f;
}
};
const int maxn=;
const int INF=0x3f3f3f3f;
struct Dinic
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
int d[maxn];
int cur[maxn];
bool vis[maxn];
void AddEdge(int from,int to, int cap)
{
edges.push_back(Edge(from,to,cap,));
edges.push_back(Edge(to,from,,));
m=edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
}
bool BFS()
{
memset(vis,,sizeof(vis));
queue<int> Q;
Q.push(s);
d[s]=;
vis[s]=;
while(!Q.empty())
{
int x=Q.front();
Q.pop();
for(int i=;i<G[x].size();i++)
{
Edge& e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=;
d[e.to]=d[x]+;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a)
{
if(x==t||a==) return a;
int flow=,f;
for(int& i=cur[x];i<G[x].size();i++)
{
Edge& e=edges[G[x][i]];
if(d[x]+==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)
{
e.flow+=f;
edges[G[x][i]^].flow-=f;
flow+=f;
a-=f;
if(a==) break;
}
}
return flow;
}
int Maxflow(int s,int t)
{
this->s=s;this->t=t;
int flow=;
while(BFS())
{
memset(cur,,sizeof(cur));
flow+=DFS(s,INF);
}
return flow;
}
}fuck;
int main()
{
int n,m,k,i,j,tmpn,x;
scanf("%d%d%d",&n,&m,&k);
for(i=;i<=n;i++)
{
fuck.AddEdge(,i+,);
fuck.AddEdge(,i+,);
}
fuck.AddEdge(,,k);
for(i=;i<=n;i++)
{
scanf("%d",&tmpn);
for(j=;j<=tmpn;j++)
{
scanf("%d",&x);
fuck.AddEdge(i+,n++x,);
}
}
for(i=;i<=m;i++)
fuck.AddEdge(n++i,n+m+,);
printf("%d\n",fuck.Maxflow(,n+m+));
return ;
}

最新文章

  1. JavaScript的前世今生
  2. Java数据结构之字符串模式匹配算法---KMP算法
  3. PHP简单文件上传
  4. 妹味6:ajax与ajax封装
  5. 【WEB API项目实战干货系列】- 接口文档与在线测试(二)
  6. Redis的安装及配置
  7. SQL数据库文件修复/用友/金蝶/管家婆/速达/思讯数据库恢复 硬盘恢复
  8. sql语句,实践证明了某种情况下not in的效率高于not exists
  9. phpstudy升级mysql数据库
  10. iOS学习——iOS原生实现二维码扫描
  11. Hive数据仓库笔记(三)
  12. 零散Linux命令
  13. Java:配置环境(Mac)——JDK
  14. java基础知识—类和对象
  15. dede网站安全要做的四件事
  16. [luogu3939][数颜色]
  17. SpringBoot集成原生redis
  18. Laravel 怎么在 blade 视图中将带 HTML 字符原样输出
  19. 如何用Caffe训练自己的网络-探索与试验
  20. python中dir(),__dict__

热门文章

  1. Lazarus 1.6 增加了新的窗体编辑器&mdash;&mdash;Sparta_DockedFormEditor.ipk
  2. vue上传阿里云图片组件
  3. ES6学习历程(字符串的扩展)
  4. [LUOGU] 4933 大师
  5. 6 DataFrame处理丢失数据--数据清洗
  6. 【codeforces 508C】Anya and Ghosts
  7. [Usaco2007 Dec]队列变换
  8. springCloud学习-断路器(Hystrix)
  9. shell函数返回值
  10. 洛谷—— P2733 家的范围 Home on the Range