美文网首页
2018-acmicpc-南京 I-Magic Potion

2018-acmicpc-南京 I-Magic Potion

作者: 阿臻同学 | 来源:发表于2019-03-30 23:11 被阅读0次

    题意

    给定n个英雄,m个怪兽,k个药水。
    每个英雄只能杀死给定集合中的一个怪兽,使用药水后可以多杀一个,每个英雄最多使用一个药水。
    https://codeforces.com/gym/101981/problem/I

    关键词

    二分图匹配、最大流、匈牙利算法、Dinic

    思路

    • 二分图匹配:将英雄点划分为一个集合,怪兽点划分为一个集合,求两次最大匹配,第一次直接求最大匹配 cnt1,求完后去除第一次最大匹配中的怪兽点,再求一次最大匹配 cnt2,最终结果为 cnt1 + min(k, cnt2)。这样写会一直Wrong answer on test 7,听说原因为:第一求完最大匹配后的图,不一定能求出第二次最大匹配的最优解,需要在第一次求完最大匹配后进行一个排序,较为复杂。
    • 最大流:数据量不大,直接邻接矩阵建图,Dinic求最大流。

    建图

    案例1最大流建图

    1 - n表示英雄,n+1 - m+n 表示怪兽, 0表示起点(简称S点), n+m+1表示终点(E点),n+m+2表示K瓶药水所代表的点(K点)。

    说明
    • 起点 -> K点的边,流量为k,其他边流量为1:象征最多使用k瓶药水。
    • K点 -> 英雄点,流量为1:每个英雄最多使用一瓶药水。
    • 怪兽点 -> E点,流量为1:每个怪兽最多只能被杀一次。

    代码

    #include <bits/stdc++.h>
    
    #define Debug 0
    #define MAXN 1056
    #define MAXM 2600
    #define MOD 1000000007
    #define INF 0x3f3f3f3f
    #define PI 3.1415926535
    #define pb push_back
    #define SYNC ios::sync_with_stdio(false);
    //#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
    typedef long long ll;
    typedef std::pair<int, int> Pair;
    
    using namespace std;
    
    int n, m, k;
    int S, E, K;
    int G[MAXN][MAXN];
    int dep[MAXN];
    
    void add_edge (int u, int v, int f)
    {
     // 依题意,单向边,双向会WA
    //    G[u][v] = G[v][u] = f; 
        G[u][v] = f;
    }
    
    bool bfs (int s, int e)
    {
        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 = G[u][i];
                if (v != u && dep[v] == -1 && flow > 0)
                {
                    dep[v] = dep[u] + 1;
                    que.push(v);
                }
    
            }
        }
        return dep[e] != -1;
    }
    
    int dfs (int u, int flow)
    {
        if (u == E || flow == 0)
        {
            return flow;
        }
        int max_flow = 0, find_flow;
        for (int i = 0; i < MAXN; ++i)
        {
            int v = i;
            int f = G[u][i];
            if (v != u && f > 0 && dep[v] == dep[u] + 1)
            {
                find_flow = dfs(v, min(flow - max_flow, f));
                if (find_flow > 0)
                {
                    G[u][v] -= find_flow;
                    G[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 max_flow = 0;
        while (bfs(S, E))
        {
            max_flow += dfs(S, INF);
        }
        return max_flow;
    }
    
    int main ()
    {
    
    #ifdef FILE_IN
        freopen(FILE_IN, "r", stdin);
    #endif
    //    SYNC
    
        cin >> n >> m >> k;
        S = 0, E = n + m + 1, K = n + m + 2;
        memset(G, 0, sizeof(G));
        add_edge(S, K, k);
        for (int i = 1; i <= n; ++i)
        {
            add_edge(S, i, 1);
            add_edge(K, i, 1);
            int t;
            cin >> t;
            for (int j = 0; j < t; ++j)
            {
                int v;
                cin >> v;
                add_edge(i, n + v, 1);
            }
    
        }
        for (int i = 1; i <= m; ++i)
        {
            add_edge(i + n, E, 1);
        }
    
        int ans = dinic();
    
        cout << ans << endl;
    
    #ifdef FILE_IN
        fclose(stdin);
    #endif
    
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:2018-acmicpc-南京 I-Magic Potion

          本文链接:https://www.haomeiwen.com/subject/parebqtx.html