Magic Potion

迈不过友情╰ 2022-04-15 03:12 197阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：n个人，m个怪物，k瓶药水，每个人可以打死对应的集合里面的一个怪物，一碰药水可以让一个人多打死一个怪物，每个人最多只能用一瓶药水，问最多能打死多少个怪物。   分析：网络流建模问题，一种思路是：源点连人容量为1，人连怪物容量为1，怪物连汇点容量为1，源点连中转点容量为k，中转点连人容量为1。第二种思路是：从源点到英雄分别拉容量为1和2的边，跑两遍网络流，判断两次的大小和k的大小，假设第一次跑完流量为a，第二次跑完流量为b ,如果a+k>=b，那么答案肯定是b，因为每个英雄最多杀两个怪兽，而第二次网络流就是基于每个英雄能杀两次怪兽而建模的，如果a+k<b，那答案肯定是a+k。 ##

## 代码（思路二）： ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #define inf 0x3f3f3f3f3f3f3f3f
    #define ll long long
    #define MAXN 10005
    using namespace std;
    int n,m,k;//点数、边数
    int sp,tp;//原点、汇点
    struct node
    {
        int v,next;
        ll cap;
    } mp[MAXN*10];
    int pre[MAXN],dis[MAXN],cur[MAXN];//cur为当前弧优化，dis存储分层图中每个点的层数（即到原点的最短距离），pre建邻接表
    int cnt=0;
    void init()//不要忘记初始化
    {
        cnt=0;
        memset(pre,-1,sizeof(pre));
    }
    void add(int u,int v,int w)//加边
    {
        mp[cnt].v=v;
        mp[cnt].cap=w;
        mp[cnt].next=pre[u];
        pre[u]=cnt++;
    }
    bool bfs()//建分层图
    {
        memset(dis,-1,sizeof(dis));
        queue<int>q;
        while(!q.empty())
            q.pop();
        q.push(sp);
        dis[sp]=0;
        int u,v;
        while(!q.empty())
        {
            u=q.front();
            q.pop();
            for(int i=pre[u]; i!=-1; i=mp[i].next)
            {
                v=mp[i].v;
                if(dis[v]==-1&&mp[i].cap>0)
                {
                    dis[v]=dis[u]+1;
                    q.push(v);
                    if(v==tp)
                        break;
                }
            }
        }
        return dis[tp]!=-1;
    }
    ll dfs(int u,ll cap)//寻找增广路
    {
        if(u==tp||cap==0)
            return cap;
        ll res=0,f;
        for(int &i=cur[u]; i!=-1; i=mp[i].next)
        {
            int v=mp[i].v;
            if(dis[v]==dis[u]+1&&(f=dfs(v,min(cap-res,mp[i].cap)))>0)
            {
                mp[i].cap-=f;
                mp[i^1].cap+=f;
                res+=f;
                if(res==cap)
                    return cap;
            }
        }
        if(!res)
            dis[u]=-1;
        return res;
    }
    ll dinic()
    {
        ll ans=0;
        while(bfs())
        {
            for(int i=0; i<=n+m+2; i++)
                cur[i]=pre[i];
            ans+=dfs(sp,inf);
        }
        return ans;
    }
    int main()
    {
        while(~scanf("%d%d%d",&n,&m,&k))
        {
            int u,v,t;
            init();
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&t);
                for(int j=1;j<=t;j++) {
                    scanf("%d",&u);
                    add(i,n+u,1);
                    add(n+u,i,0);
                }
            }
            for(int i=1;i<=m;i++) {
                add(n+i,n+m+2,1);
                add(n+m+2,n+i,0);
            }
            for(int i=1;i<=n;i++) {
                add(0,i,1);
                add(i,0,0);
            }
            add(0,n+m+1,k);
            add(n+m+1,0,0);
            for(int i=1;i<=n;i++) {
                add(n+m+1,i,1);
                add(i,n+m+1,0);
            }
            sp=0;
            tp=n+m+2;
            ll ans=dinic();
            printf("%lld\n",ans);
        }
        return 0;
    }

[Link 1]: http://codeforces.com/gym/101981/attachments/download/7891/20182019-acmicpc-asia-nanjing-regional-contest-en.pdf