2018icpc南京现场赛-I Magic Potion(最大流)

题意：

n个英雄，m个怪兽，第i个英雄可以打第i个集合里的怪兽，一个怪兽可以在多个集合里

有k瓶药水，每个英雄最多喝一次，可以多打一只怪兽，求最多打多少只

n,m,k<=500

思路：

最大流，建图方式：

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

//#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#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<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e6+;

const int maxm = 2e6+;

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_i

int n, m, s, t, tot, maxflow;

queue<int>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]=,Next[tot]=head[y],head[y]=tot;

}

bool bfs(){

    mem(d,);

    while(!q.empty())q.pop();

    q.push(s);

    d[s]=;

    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] + ;

            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]+){

            k = dinic(ver[i], min(rest, edge[i]));

            if(!k) d[ver[i]] = ;

            edge[i] -= k;

            edge[i^] += k;

            rest -= k;

        }

    }

    return flow - rest;

}

int main(){

    int num;

    scanf("%d %d %d", &n, &m, &num);

    tot = ;

    //scanf("%d %d", &s, &t);

    s = ;

    t = n+m+;

    add(s,,num);

    for(int i = ; i <= n; i++){

        int sz, x;

        add(s,+i,);

        add(,+i,);

        scanf("%d", &sz);

        for(int j = ; j <= sz; j++){

            scanf("%d", &x);

            add(+i,+n+x,);

        }

    }

    for(int i = ; i <= m; i++){

        add(+n+i,t,);

    }

    int flow = ;

    maxflow=;

    while(bfs()){

        while(){

            flow = dinic(s,inf);

            if(!flow)break;

            maxflow+=flow;

        }

    }

    printf("%d\n",maxflow);

    return ;

}

/*

3 5 0

4 1 2 3 5

2 2 5

2 1 2

5 10 2

2 3 10

5 1 3 4 6 10

5 3 4 6 8 9

3 1 9 10

5 1 3 6 7 10

 */