1039 AlvinZH的学霸养成记IV

思路

难题，最大二分图匹配。

难点在于如何转化问题，n对n，一个只能攻击一个，判断是否存在一种攻击方案我方不死团灭对方。可以想到把所有随从看作点，对于可攻击的两个随从间连上边，这样就把问题转化为图了。

需要注意的是属性值的转化：免疫可看做生命值无限，剧毒可看做攻击力无限。（需要一点小小的机智）

图建好了，接下来怎么办呢？假设存在一种方案满足题意，那就是每个我方随从都可以找到敌方随从攻击，由于要团灭，只能存在一对一的情况，不存在多对一或一对多。如何表达这个方案呢？边！没错，就是刚才连起来的边的一个子集。这个子集有一个特点：n对n，n条边，边连着两边，且没有公共顶点。

没错，经过一番分析，最大二分图匹配已经很明显了。求解过程套板子就好了。

分析

二分图匹配算法

1.匈牙利算法：其本质就是，有条件就上，没条件创造条件也要上。DFS与BFS都可，时间复杂度均为 \(O(V⋅E)\) 。实际对于稀疏图BFS更佳。

2.Hopcroft-Karp算法：匈牙利算法的改进版，每次寻找多条增广路径。时间复杂度可以到达 \(O(n^{0.5}*m)\) 。

3.Dinic算法：二分图匹配其实是一个最大流问题，Dinic是一种优化过的求解最大流算法。与朴素的FF算法（\(O(n*m^2)\)）不同，其可以同时多路增广。求解二分图时，构建超级源点和超级汇点，匹配边权值为1，求最大流即可。理论最坏复杂度为 \(O(n^2m)\) ，稠密图时比匈牙利DFS快了不少。

参考博客：;

;

;

参考代码（DFS）

//// Created by AlvinZH on 2017/11/27.// Copyright (c) AlvinZH. All rights reserved.//#include 
    
     #include 
     
      #include 
      
       #define MaxSize 1005#define INF 0x3f3f3f3fusing namespace std;int n, ans;vector
       
         G[MaxSize];//记录可攻击的敌方随从int match[MaxSize];//记录匹配点int visit[MaxSize];//记录是否访问struct minion {    int attack, life;}A[MaxSize], B[MaxSize];bool dfs(int x)//寻找增广路径{    for (int i = 0; i < G[x].size(); ++i)    {        int to = G[x][i];        if(!visit[to])        {            visit[to] = 1;            if(!match[to] || dfs(match[to]))            {                match[to] = x;                return true;            }        }    }    return false;}int MaxMatch(){    ans = 0;    memset(match, 0, sizeof(match));    for (int i = 1; i <= n; ++i)    {        memset(visit, 0, sizeof(visit));//清空访问        if(dfs(i)) ans++;//从节点i尝试扩展    }    return ans;}int main(){    while(~scanf("%d", &n))    {        int a, l, p;        for (int i = 1; i <= n; ++i) {            scanf("%d %d %d", &a, &l, &p);            switch (p) {                case 0:                    A[i].attack = a; A[i].life = l; break;                case 1:                    A[i].attack = a; A[i].life = INF; break;                case 2:                    A[i].attack = INF; A[i].life = l; break;                case 3:                    A[i].attack = INF; A[i].life = INF; break;                default:                    break;            }        }        for (int i = 1; i <= n; ++i)            scanf("%d %d", &B[i].attack, &B[i].life);        for (int i = 1; i <= n; ++i)            G[i].clear();        for (int i = 1; i <= n; ++i) {            for (int j = 1; j <= n; ++j) {                if(A[i].attack >= B[j].life && A[i].life > B[j].attack)                    G[i].push_back(j);            }        }        if(n == MaxMatch()) printf("YES\n");        else printf("NO\n");    }}