有 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