首页 > 其他分享 >Magic Potion Gym - 101981I

Magic Potion Gym - 101981I

时间:2023-03-26 13:35:00浏览次数:45  
标签:nxt Potion Magic int Gym go now hd dis

有 n 个人,m 个怪兽,k 瓶药水,现在依次给出每个人可以杀的怪物的数量 t 以及怪物的编号,

每个人只能杀他能杀的一个怪物,但可以领取一瓶药水复活再杀一个(只能领取一次),问最多能杀死的怪物

 

最大流

建图:

 S--> 人(1) , S->S+1(K) , S+1 --> 人 (1) ,

人--》怪物(1) , 怪物--》T(1)

 

 

#include<iostream>
#include<queue> 
#include<cstring>
#define IOS std::ios::sync_with_stdio(0)
using namespace std;
 const int N =1030,M=5e5+100;
 //#define int long long
 const int inf=1e18;
 int all=1,hd[N],go[M],w[M],nxt[M];
 
 int S,T,n,m,K;
 int dis[M],ans=0,now[M];
 
 void add_(int x,int y,int z){
 	nxt[++all]=hd[x]; hd[x]=all; go[all]=y;
 	w[all]=z;
 	swap(x,y);
 	nxt[++all]=hd[x]; hd[x]=all; go[all]=y;
 	w[all]=0;
 }
 bool bfs(){
 	for(int i=1;i<=n+m+3;i++)dis[i]=inf;
 	queue<int> q;
 	q.push(S);
 	now[S]=hd[S];
 	dis[S]=0;
 	
 	while(q.empty()==0){
 		int x=q.front(); 
 		q.pop();
 		for(int i=hd[x];i;i=nxt[i]){
 			int y=go[i];
 			if(w[i]>0&&dis[y]==inf){
 				dis[y]=dis[x]+1;
 				now[y]=hd[y];
	 			q.push(y);
	 			if(y==T) return 1;
 			}
 		}
 	}
 	return 0;
 }
 int dfs(int x,int sum){
 	if(x==T) return sum;
 	int k,res=0;
 	
 	for(int i=now[x];i&∑i=nxt[i]){
 		now[x]=i;
 		int y=go[i]; 
 		if(w[i]>0&&(dis[y]==dis[x]+1)){
 			k=dfs(y,min(sum,w[i]));
 			if(k==0) dis[y]=inf;
 			w[i]-=k;
 			w[i^1]+=k;
 			res+=k;
 			sum-=k;
 		}
 	}
 	return res;
 }
 
 signed main(){
 	IOS;
 	int t,x,i;
 	cin>>n>>m>>K;
 	S=n+m+1,T=n+m+3;
 	for(i=1;i<=n;i++){
 		add_(S,i,1); add_(S+1,i,1);
 	}
 	add_(S,S+1,K);
 	
 	for(i=1;i<=n;i++){
 		cin>>t;
 		while(t--) cin>>x,add_(i,n+x,1);
 	}
 	for(i=n+1;i<=n+m;i++) add_(i,T,1);
 	
 	int ans=0;
 	while(bfs()) ans+=dfs(S,inf);
 	cout<<ans<<endl;
 }
 
 
 
 

 

标签:nxt,Potion,Magic,int,Gym,go,now,hd,dis
From: https://www.cnblogs.com/towboa/p/17258525.html

相关文章

  • 「Gym102759B」Cactus Competition 题解
    传送门「Gym102759B」CactusCompetition题目大意有一个\(n\timesm\)的网格图,一个长度为\(n\)的序列\(a\),和一个长度为\(m\)的序列\(b\)。网格图中,第\(i\)......
  • magic-byte转对象中需要注意的一些坑
    公司有对接网络设备的需要,由于协议是自己定的。所以对象在序列化时也需要自己序列化。很麻烦,在网上搜索了一圈。找到了一个框架,可以通过注解来申明序列化过程。用起......
  • 35. CF-Kaavi and Magic Spell
    链接这个区间dp的状态设计很巧妙。dp[i][j]表示用\(s\)的长度为\(j-i+1\)的前缀组成\([t_i\cdotst_j]\)的子串方案数。然后转移就是普通的区间dp的转移了。初始......
  • 1774F1 - Magician and Pigs (Easy Version)
    1774F1-MagicianandPigs(EasyVersion)思路1)3操作其实就是,把原有的猪都减去一个总的sum,然后加上原来自己的值,之后sum会翻倍。也就是sum太大之后,就不变了,因为减去......
  • RL 基础:如何搭建自定义 gym 环境
    需实现的方法:__init__(self):需定义action_space和observation_space,使用space.Box之类来表示(fromgymimportspaces)。step(self,action):返回observation......
  • Gym100078H-History-of-Football题解
    题目传送门题意:有\(n\)支球队,每两支球队之间都会进行一场较量,赢者积\(3\)分,输者积\(0\)分,如果平局则各积\(1\)分。给出每支球队的最终积分,求方案数。\(n\le8\)......
  • Gym100753D-Carpets题解
    题目传送门题意:有一个\(H\timesW\)的地板和\(n\)个矩形地毯,问是否能不重不漏地填满地板。\(H,W\le100,n\le7\)。考虑朴素的搜索,每次考虑最左上角的没填的位置,枚......
  • Gym100825C-KenKen-You-Do-It题解
    题目传送门题意:在一个矩阵上选中了若干个格子,保证连通。你需要在这些格子中填数,使得:每行每列不能重复,且这些数进行给定运算(可以认为只有加法和乘法)的结果为给定的数值。......
  • Gym100959I-Robots题解
    题意:平面直角坐标系上有\(n\)个机器人,每个机器人有一个上下左右之一的方向,初始所有机器人静止。在第\(0\)秒,你让第一个机器人开始朝它的方向移动,速度为每秒一个单位。......
  • Gym101252B-Kakuro题解
    题目传送门题意:有一个矩阵,每个格子为黑色或白色。你需要向白色格子中填\(1\sim9\)的整整睡。从某一个黑色格子的右侧往右连续的一段极长的白色格子被称为一个run,往下......