当前位置:网站首页>[CF Gym101196-I] Waif Until Dark 网络最大流
[CF Gym101196-I] Waif Until Dark 网络最大流
2022-07-06 07:22:00 【PushyTao】
题目链接
输入
4 3 1
2 1 2
2 1 2
1 3
1 3
2 1 2 1
输出
2
题目大意:
小孩要玩玩具,一些玩具是属于一定的种类的
但是小孩只能够玩每种种类的一部分玩具,并且小孩并不会喜欢所有的玩具,每个小孩都有自己喜欢玩的玩具,问最多能够有多少个小孩被满足
输入n代表小花子的数量,m玩具的数量,p玩具种类的数量
然后是n行{
在这n行的第i行中:
每行一个k,然后是k个数,代表第i个孩子喜欢玩的k个玩具的编号
}
然后是p行{
在这p行的第i行中:
每行有一个l,然后是l个数,最后是r 代表这l个玩具属于种类i,并且这个种类最多用r个(小孩只能够玩每种种类的一部分玩具)
}
并且最重要的一句话:
Toys can be in at most one category and any toy not listed in these p lines is not in any toy category and all of them can be used. No toy number appears more than once on any line.
玩具最多属于一个种类,如果说有的玩具没有被划分到任意一个种类当中,都可以被任意的玩耍。并且保证所有的玩具只在一行中出现一次
接下来就是建图了:
确定源点和汇点分别为1001、1002
小孩要玩玩具=》将小孩和玩具之间建立容量为1的边
玩具属于{玩具的种类} =》 将玩具和种类建议容量为1的边(注意统计没有被添加在种类中的玩具,可以随便玩)
将源点与玩具的种类之间建立容量为r的边(种类最多用r个(小孩只能够玩每种种类的一部分玩具))
将源点与可以随意玩的玩具之间建立容量为1的边
最后将小孩与汇点1002相连,建立容量为1的边
最终求得源点1001与汇点1002的最大流即可获得最大的能够满足的小孩的数量
EK_code:
struct Edge {
int u, v;
ll cap, flow;
Edge(int uu, int vv, ll _cap, ll _flow) {
u = uu, v = vv, cap = _cap, flow = _flow;
}
};
struct EdmondsKarp {
ll n, m;
vector<Edge> edges;
vector<int> G[maxn];
ll a[maxn], p[maxn];
void _init(int n) {
for (int i = 0; i <= n; i++) G[i].clear();
edges.clear();
}
void add(int u, int v, ll cap) {
edges.push_back(Edge(u, v, cap, 0));
edges.push_back(Edge(v, u, 0, 0));
m = edges.size();
G[u].push_back(m - 2);
G[v].push_back(m - 1);
}
ll maxFlow(int s, int t) {
ll Flow = 0;
while (true) {
memset(a, 0, sizeof a);
queue<int> que;
que.push(s);
a[s] = INF;
while (que.size()) {
int u = que.front();
que.pop();
for (int i = 0; i < G[u].size(); i++) {
int id = G[u][i];
Edge &e = edges[id];///不加&也是可以的
int to = e.v;
if (!a[to] && e.cap > e.flow) {
p[to] = id;
a[to] = min(a[u], e.cap - e.flow);
que.push(to);
}
}
if (a[t]) break;
}
if (!a[t]) break;
for (int u = t; u != s; u = edges[p[u]].u) {
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
Flow += a[t];
}
return Flow;
}
} slove;
int n, m, s, t;
int mp[maxn];
int main() {
/** cin >> n >> m >> s >> t; slove.init(n); slove.n = n; for (int i = 1; i <= m; i++) { int u = read, v = read; ll cap = read; slove.add(u,v,cap); } cout << slove.maxFlow(s,t) <<endl; **/
int p;
n = read,m = read,p = read;
// n child m toy p cate
slove._init(1007);
for(int i=1; i<=n; i++) {
int cnt = read;
for(int j=1; j<=cnt; j++) {
int u = read;// toy id
slove.add(u,m+i,1);// child <-> toy cap = 1 ok
}
}
for(int i=1; i<=n; i++) {
slove.add(i+m, 1002, 1);// child <-> end cap = 1; ok
}
for(int i=1; i<=p; i++) {
int l = read;
for(int j=1; j<=l; j++) {
int v = read;
mp[v] = 1;
slove.add(m+n+i,v,1);// cate <-> toy cap = 1; ok
}
int amount = read;// r
slove.add(1001,n+m+i,amount);// 1001 <->cate cap = amount; ok
}
for(int i=1; i<=m; i++) {
if(mp[i] == 0) {
slove.add(1001,i,1);// 1001 <-> toy cap = 1;
}
}
int ans = slove.maxFlow(1001,1002);
cout << ans << endl;
return 0;
}
/** 4 3 1 2 1 2 2 1 2 1 3 1 3 2 1 2 1 **/
Dinic_code:
struct Edge {
int u, v;
ll cap, flow;
Edge(int _u, int _v, ll _cap, ll _flow) {
u = _u, v = _v;
cap = _cap, flow = _flow;
}
};
struct Dinic {
vector<Edge> edge;
vector<int> G[maxn];
ll dis[maxn],cur[maxn];
int n,s,t;
bool vis[maxn];
void init(int x,int _s,int _t){
n = x;
for(int i = 0;i <= n;i++) G[i].clear();
s = _s,t = _t;
edge.clear();
}
void add(int u,int v,ll cap){
edge.push_back(Edge(u,v,cap,0));
edge.push_back(Edge(v,u,0,0));
G[u].push_back(edge.size() - 2);
G[v].push_back(edge.size() - 1);
}
bool bfs(int s,int t){
queue<int> que;
memset(vis,0,sizeof vis);
// memset(dis,0,sizeof dis);
dis[s] = 0;
que.push(s);
vis[s] = 1;
while(que.size()){
int u = que.front();
que.pop();
for(int i=0;i<G[u].size();i++){
int id = G[u][i];
int to = edge[id].v;
if(!vis[to] && edge[id].cap > edge[id].flow){
dis[to] = dis[u] + 1;
que.push(to);
vis[to] = 1;
}
}
}
return vis[t];
}
ll dfs(int s,int t,ll rest){
if(s == t || rest == 0) return rest;
ll sum = 0LL;
ll Flow = 0, f;
for(ll& i = cur[s];i < G[s].size();i ++){
Edge& e = edge[G[s][i]];
if(dis[s] + 1 == dis[e.v] && (f = dfs(e.v ,t,min(rest,e.cap - e.flow))) > 0){
e.flow += f;
edge[G[s][i] ^ 1].flow -= f;
Flow += f;
rest -= f;
if(rest == 0) break;
}
}
return Flow;
}
ll getMaxFlow(int s,int t){
ll ans = 0;
while(bfs(s,t)) {
memset(cur,0,sizeof cur);
ans += dfs(s,t,0x3f3f3f3f);
}
return ans;
}
} solve;
int mp[1007];
int main() {
int n = read,m = read,p = read;
solve.init(1000,1001,1002);
for(int i=1; i<=n; i++) {
int cnt = read;
for(int j=1; j<=cnt; j++) {
int u = read;// toy id
solve.add(u,m+i,1);// child <-> toy cap = 1 ok
}
}
for(int i=1; i<=n; i++) {
solve.add(i+m, 1002, 1);// child <-> end cap = 1; ok
}
for(int i=1; i<=p; i++) {
int l = read;
for(int j=1; j<=l; j++) {
int v = read;
mp[v] = 1;
solve.add(m+n+i,v,1);// cate <-> toy cap = 1; ok
}
int amount = read;// r
solve.add(1001,n+m+i,amount);// 1001 <-> cate cap = amount; ok
}
for(int i=1; i<=m; i++) {
if(mp[i] == 0) {
solve.add(1001,i,1);// 1001 <-> toy cap = 1;
}
}
int ans = solve.getMaxFlow(1001,1002);
cout << ans << endl;
return 0;
}
/** **/
边栏推荐
- First knowledge of OpenGL es learning (1)
- TS Basics
- TypeScript 可索引类型
- mysql如何合并数据
- Go learning -- implementing generics based on reflection and empty interfaces
- 【mysql学习笔记30】锁(非教程)
- Introduction to the basics of network security
- Jerry's ad series MIDI function description [chapter]
- 树莓派串口登录与SSH登录方法
- Get/post/put/patch/delete meaning
猜你喜欢
Markdown 中设置图片图注
The best way to learn SEO: search engine
Upgraded wechat tool applet source code for mobile phone detection - supports a variety of main traffic modes
idea控制台彩色日志
杰理之BLE【篇】
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
树莓派3B更新vim
C - Inheritance - polymorphism - virtual function member (lower)
首发织梦百度推送插件全自动收录优化seo收录模块
学go之路(一)go的基本介绍到第一个helloworld
随机推荐
Lesson 12 study notes 2022.02.11
Crawling exercise: Notice of crawling Henan Agricultural University
【mysql学习笔记30】锁(非教程)
Multi attribute object detection on rare aircraft data sets: experimental process using yolov5
杰理之开发板上电开机,就可以手机打开 NRF 的 APP【篇】
#systemverilog# 可綜合模型的結構總結
Jerry needs to modify the profile definition of GATT [chapter]
多线程和并发编程(二)
巴比特 | 元宇宙每日必读:中国互联网企业涌入元宇宙的群像:“只有各种求生欲,没有前瞻创新的雄心”...
OpenJudge NOI 2.1 1749:数字方格
Thought map of data warehouse construction
Idea console color log
LeetCode Algorithm 2181. Merge nodes between zero
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Win10 64 bit Mitsubishi PLC software appears oleaut32 DLL access denied
[MySQL learning notes 32] mvcc
Typescript variable scope
Chrome view page FPS
leetcode704. Binary search (find an element, simple, different writing)
word中把带有某个符号的行全部选中,更改为标题