「LibreOJ Round #11」Misaka Network 与测试【二分图最大匹配+读入坑点】

题目链接 LOJ 569

---

  这道题的坑点或许不在于想到这个算法，而是在于这里有读入的坑点，会使得你在本地编译正确而在题目判断的时候得到WA。

  因为，题目的操作系统是win的，而我自己的编译器是Mac OS的Xcode，所以最后造成了我没法读到'\r\n'，是因为我只读了'\n'但是本地确实正确的。

  所以，这里的读入要谨慎处理一下。

  然后，就是关于这道题的思路了，很容易想到的是有2，那么就是直接取了，如果取矩形的话，肯定是取1*2大小的才是最贪心的，因为更大的矩形必然是由这样1*2大小来生成的，所以最贪心还是这样取。

  于是变成了1去找3这样的一个过程，岂不就是二分图的最大匹配了，于是，利用匈牙利算法，复杂度就是O(N*M)。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, M, tot = 0, head[maxN], cnt, val[maxN], team[maxN], t1 = 0, t2 = 0;
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxN << 3];
inline void addEddge(int u, int v)
{
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
vector<int> ID[maxN];
int link[maxN];
bool vis[maxN];
bool match(int u)
{
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(vis[v]) continue;
        vis[v] = true;
        if(!link[v] || match(link[v]))
        {
            link[v] = u;
            return true;
        }
    }
    return false;
}
int Hungery()
{
    int ans = 0;
    for(int i=1; i<=t1; i++)
    {
        for(int j=1; j<=t2; j++) vis[j] = false;
        if(match(i)) ans++;
    }
    return ans;
}
int main()
{
    scanf("%d%d", &N, &M);
    char ch;
    int ans = 0;
    for(int i=0; i<N; i++)
    {
        ID[i].resize(M + 1);
        for(int j=0; j<M; j++)
        {
            ch = getchar();
            while(!(ch == '1' || ch == '2' || ch == '3' || ch == '*')) ch = getchar();
            if(ch == '*') continue;
            ID[i][j] = ++tot; head[tot] = -1;
            val[tot] = ch - '0';
            if(val[tot] == 2) { ans++; continue; }
            if(val[tot] == 1)
            {
                team[tot] = ++t1;
                if(i && val[ID[i - 1][j]] + val[tot] == 4) addEddge(t1, team[ID[i - 1][j]]);
                if(j && val[ID[i][j - 1]] + val[tot] == 4) addEddge(t1, team[ID[i][j - 1]]);
            }
            else
            {
                team[tot] = ++t2;
                if(i && val[ID[i - 1][j]] + val[tot] == 4) addEddge(team[ID[i - 1][j]], t2);
                if(j && val[ID[i][j - 1]] + val[tot] == 4) addEddge(team[ID[i][j - 1]], t2);
            }
        }
    }
    printf("%d\n", ans + Hungery());
    return 0;
}