(Sky OJ) 153. Day 4 PG. Hard Game [二分圖]

https://pc2.tfcis.org/sky/index.php/problem/view/153/

警告：本份code的解法非官方正解，而且是用了壓常數的方法過的

本題要得答案是  (n - 最大匹配必經點) ，那，若一個點是"最大匹配必經點"，這個點就找不到增廣路徑了！

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 10006;
const int MAX_M = 3e5+ 6;

vector<short> edg[MAX_N];
int col[MAX_N];
int match[MAX_N];
bool visit[MAX_N];
bool can[MAX_N];

int limitid,limiti;

bool dfs2(short id) {
    if (id == -1) return true;
    if(id == limitid) return false;
    for (short i:edg[id]) {
        if (visit[i]) continue;
        visit[i]=1;
        if (match[i] == -1 || match[i] != limitid && dfs2(match[i])) {
            return true;
        }
    }
    return false;
}

typedef int LL;

#define short unsigned short

struct Dinic {
    static const short MAX_N = 2e4 + 6;
    struct Edge {
        short to,cap;
        int rev;
    };
    vector<Edge> edg[MAX_N];
    short n,s,t;
    void init(short _n,short _s,short _t) {
        n=_n;
        s=_s;
        t=_t;
        for (short i=0;n+1>=i;++i) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(short from,short to,short cap) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        edg[to].push_back({from,0,SZ(edg[from])-1});
    }
    int iter[MAX_N];
    short level[MAX_N];
    void BFS() {
        queue<short> que;
        memset(level,0,sizeof(level));
        level[s] = 1;
        que.push(s);
        while (!que.empty()) {
            short t=que.front();
            que.pop();
            for (Edge &e:edg[t]) {
                if (e.cap > 0 && level[e.to] == 0) {
                    level[e.to] = level[t] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    short dfs(short id,short flow) {
        if (id == t) return flow;
        for (int &i=iter[id];SZ(edg[id])>i;i++) {
            Edge &e=edg[id][i];
            if (e.cap > 0 && level[e.to] == level[id] + 1) {
                short ret=dfs(e.to,min(flow,e.cap));
                if (ret>0) {
                    e.cap -= ret;
                    edg[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    static const short INF = 60000 + 7;
    short flow() {
        short ret=0;
        while (1) {
            BFS();
            if (level[t] == 0) break;
            memset(iter,0,sizeof(iter));
            short tmp=0;
            while ((tmp = dfs(s,INF)) > 0) {
                ret += tmp;
            }
        }
        return ret;
    }
} dinic;

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    int s=0,t=2*n+1;
    dinic.init(t,s,t);
    for (int i=1;m>=i;++i) {
        int a,b;
        scanf("%d %d",&a,&b);
        dinic.add_edge(a,b+n,1);
        dinic.add_edge(b,a+n,1);
        edg[a].push_back(b);
        edg[b].push_back(a);
    }
    for (int i=1;n>=i;++i) {
        dinic.add_edge(s,i,1);
    }
    for (int i=1;n>=i;++i) {
        dinic.add_edge(i+n,t,1);
    }
    int ans=0;
    dinic.flow();
    memset(match,-1,sizeof(match));
    for (int i=1;n>=i;++i) {
        for (auto e:dinic.edg[i]) {
            if (e.to > i && e.cap == 0) {
                match[e.to-n] = i;
            } 
        }
    }
    for (int i=1;n>=i;++i) {
        if (match[i] == -1) ++ans;
        else {
            memset(visit,0,sizeof(visit));
            if(dfs2(match[i])) ++ans;
        }
    }
    printf("%d\n",ans);
}