题意: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 ;
}