Gym - 101981I The 2018 ICPC Asia Nanjing Regional Contest I.Magic Potion 最大流
2024-08-26 21:09:21
题意: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 ;
}
最新文章
- JavaScript的前世今生
- Java数据结构之字符串模式匹配算法---KMP算法
- PHP简单文件上传
- 妹味6:ajax与ajax封装
- 【WEB API项目实战干货系列】- 接口文档与在线测试(二)
- Redis的安装及配置
- SQL数据库文件修复/用友/金蝶/管家婆/速达/思讯数据库恢复 硬盘恢复
- sql语句,实践证明了某种情况下not in的效率高于not exists
- phpstudy升级mysql数据库
- iOS学习——iOS原生实现二维码扫描
- Hive数据仓库笔记(三)
- 零散Linux命令
- Java:配置环境(Mac)——JDK
- java基础知识—类和对象
- dede网站安全要做的四件事
- [luogu3939][数颜色]
- SpringBoot集成原生redis
- Laravel 怎么在 blade 视图中将带 HTML 字符原样输出
- 如何用Caffe训练自己的网络-探索与试验
- python中dir(),__dict__
热门文章
- Lazarus 1.6 增加了新的窗体编辑器&mdash;&mdash;Sparta_DockedFormEditor.ipk
- vue上传阿里云图片组件
- ES6学习历程(字符串的扩展)
- [LUOGU] 4933 大师
- 6 DataFrame处理丢失数据--数据清洗
- 【codeforces 508C】Anya and Ghosts
- [Usaco2007 Dec]队列变换
- springCloud学习-断路器(Hystrix)
- shell函数返回值
- 洛谷—— P2733 家的范围 Home on the Range