本文共 2275 字，大约阅读时间需要 7 分钟。
题意：
n个英雄，m个怪兽，第i个英雄可以打第i个集合里的怪兽，一个怪兽可以在多个集合里
有k瓶药水，每个英雄最多喝一次，可以多打一只怪兽，求最多打多少只
n,m,k<=500
思路：
最大流，建图方式：
代码：
#include #include #include #include #include #include //#include #include #include #include #include #include #include #define fst first#define sc second#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))#define lson l,mid,root<<1#define rson mid+1,r,root<<1|1#define lc root<<1#define rc root<<1|1#define lowbit(x) ((x)&(-x)) using namespace std;typedef double db;typedef long double ldb;typedef long long ll;typedef unsigned long long ull;typedef pair PI;typedef pair PLL;const db eps = 1e-6;const int mod = 1e9+7;const int maxn = 2e6+100;const int maxm = 2e6+100;const int inf = 0x3f3f3f3f;const db pi = acos(-1.0);int head[maxn],d[maxn];//层int ver[maxm],edge[maxm],Next[maxm];//edge[i]: c for edge_iint n, m, s, t, tot, maxflow;queue q;int vis[maxn];//出现过void add(int x, int y, int z){ ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot; ver[++tot]=x,edge[tot]=0,Next[tot]=head[y],head[y]=tot;}bool bfs(){ mem(d,0); while(!q.empty())q.pop(); q.push(s); d[s]=1; while(!q.empty()){ int x = q.front(); q.pop(); for(int i = head[x]; i; i = Next[i]){ if(edge[i] && !d[ver[i]]){ q.push(ver[i]); d[ver[i]] = d[x] + 1; if(ver[i] == t) return true; } } } return false;}int dinic(int x, int flow){ if(x==t) return flow; int rest = flow, k; for(int i = head[x]; i; i = Next[i]){ if(edge[i] && d[ver[i]] == d[x]+1){ k = dinic(ver[i], min(rest, edge[i])); if(!k) d[ver[i]] = 0; edge[i] -= k; edge[i^1] += k; rest -= k; } } return flow - rest;}int main(){ int num; scanf("%d %d %d", &n, &m, &num); tot = 1; //scanf("%d %d", &s, &t); s = 1; t = n+m+3; add(s,2,num); for(int i = 1; i <= n; i++){ int sz, x; add(s,2+i,1); add(2,2+i,1); scanf("%d", &sz); for(int j = 1; j <= sz; j++){ scanf("%d", &x); add(2+i,2+n+x,1); } } for(int i = 1; i <= m; i++){ add(2+n+i,t,1); } int flow = 0; maxflow=0; while(bfs()){ while(1){ flow = dinic(s,inf); if(!flow)break; maxflow+=flow; } } printf("%d\n",maxflow); return 0;}/*3 5 04 1 2 3 52 2 52 1 25 10 22 3 105 1 3 4 6 105 3 4 6 8 93 1 9 105 1 3 6 7 10 */
转载于:https://www.cnblogs.com/wrjlinkkkkkk/p/10037923.html
