题意：
给定n个英雄，m个怪兽，k个药水。
每个英雄只能杀死给定集合中的一个怪兽，使用药水后可以多杀一个，每个英雄最多使用一个药水。
题解：
1 - n表示英雄，n+1 - m+n 表示怪兽， 0表示起点（简称s点）， n+m+1表示终点（t点），n+m+2表示K瓶药水所代表的点（kk点）。
起点 -> kk点的边，流量为k，其他边流量为1：象征最多使用k瓶药水。
kk点 -> 英雄点，流量为1：每个英雄最多使用一瓶药水。
怪兽点 -> t点，流量为1：每个怪兽最多只能被杀一次。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxm=1e6+5; const int maxn=2005; int n,m,k; struct node{ ll t,cap,flow,next; //cap容量，flow流量 }e[maxm]; int head[maxn],cur[maxn],cnt; //cur优化dfs中的head void add(int u,int v,int cap) //u->v容量为cap { e[cnt]=node{v,cap,0,head[u]}; head[u]=cnt++; e[cnt]=node{u,0,0,head[v]};//容量为0的反向边 head[v]=cnt++; } int dep[maxn]; //bfs深度 bool bfs(int s,int t) //O(n+m) { memset(dep,0,sizeof(dep)); queue<int>q; q.push(s); dep[s]=1; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];~i;i=e[i].next) { int v=e[i].t; if(dep[v]==0&&e[i].cap-e[i].flow>0) { dep[v]=dep[u]+1; q.push(v); } } } return dep[t]>0; //存在增广路 } ll dfs(int s,int t,ll minedge) { if(s==t)return minedge; ll flow=0; //从当前s点流出的流量 for(int &i=cur[s];~i;i=e[i].next) { int v=e[i].t; if(dep[v]==dep[s]+1&&e[i].cap-e[i].flow>0) //层次关系&&有剩余流量 { ll temp=dfs(v,t,min(minedge-flow,e[i].cap-e[i].flow)); e[i].flow+=temp; //流量增加 e[i^1].flow-=temp; //反向边流量减少 flow+=temp; //flow已分配的流量 if(flow==minedge)return flow; //已达到祖先的最大流，无法再大，剪枝 } } if(flow==0)dep[s]=0; //此点已无流，标记掉 return flow; } ll dinic(int s,int t) //一定要建立反向边cap=0 { ll maxflow=0; while(bfs(s,t)) //有增广路 { memcpy(cur,head,sizeof(head)); //重要的优化 maxflow+=dfs(s,t,inf); } return maxflow; } void init() { memset(head,-1,sizeof head); cnt=0; } int main() { int m, n, k; int x, y; init(); scanf("%d %d %d", &n, &m, &k); int s = 0, t = n+m+1, kk = n+m+2; add(s, kk, k); for(int i = 1; i <= n; i++) { add(s, i, 1); add(kk, i, 1); scanf("%d", &x); for(int j = 0; j < x; j++) { scanf("%d", &y); add(i, y + n, 1); } } for(int i=1;i<=m;i++)add(i+n,t,1); int ans = dinic(s, t); printf("%d\n", ans); return 0; }
#include<bits/stdc++.h>//最大流 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1055; using namespace std; int n, m, k; int mmp[maxn][maxn]; int dep[maxn]; void add (int u, int v, int w) { mmp[u][v] = w; } bool bfs (int s, int t) { memset(dep, -1, sizeof(dep)); queue<int> que; dep[s] = 0; que.push(s); while (!que.empty()) { int u = que.front(); que.pop(); for (int i = 0; i < maxn; ++i) { int v = i; int flow = mmp[u][i]; if (v != u && dep[v] == -1 && flow > 0) { dep[v] = dep[u] + 1; que.push(v); } } } return dep[t] != -1; } int dfs (int u, int t,int flow) { if (u == t || flow == 0) { return flow; } int max_flow = 0, find_flow; for (int i = 0; i < maxn; ++i) { int v = i; int f = mmp[u][i]; if (v != u && f > 0 && dep[v] == dep[u] + 1) { find_flow = dfs(v, t,min(flow - max_flow, f)); if (find_flow > 0) { mmp[u][v] -= find_flow; mmp[v][u] += find_flow; max_flow += find_flow; if (max_flow == flow) return flow; } } } if (max_flow == 0) dep[u] = -1; return max_flow; } int dinic (int s,int t) { int max_flow = 0; while (bfs(s, t)) { max_flow += dfs(s,t,inf); } return max_flow; } int main () { scanf("%d%d%d",&n,&m,&k); int s = 0, t = n + m + 1, kk = n + m + 2; memset(mmp, 0, sizeof(mmp)); add(s, kk, k); for (int i = 1; i <= n; ++i) { add(s, i, 1); add(kk, i, 1); int x; scanf("%d",&x); for (int j = 0; j < x; ++j) { int v; scanf("%d",&v); add(i, n + v, 1); } } for (int i = 1; i <= m; ++i) { add(i + n, t, 1); } int ans = dinic(s,t); printf("%d\n",ans); return 0; }