记录编号	396316	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 搭配飞行员	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-04-18 18:17:25	内存使用	0.49 MiB

#include <bits/stdc++.h>
#define MAXN 105
#define inf 0xfffffff
using namespace std;

inline void File() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
#else 
    freopen("flyer.in", "r", stdin);
    freopen("flyer.out", "w", stdout);
#endif
}

inline int get_num() {
    int k = 0;
    char c = getchar();
    for(; !isdigit(c); c = getchar());
    for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
    return k;
}

struct edge {
    int fr, to, v, ne;
    edge() {;}
    edge(int fr_, int to_, int v_, int ne_) {
        fr = fr_, to = to_, v = v_, ne = ne_;
    }
}e[MAXN * (MAXN + 3)];

int cnt, head[MAXN];

inline void addedge(int fr, int to, int v) {
    e[cnt++] = edge(fr, to, v, head[fr]), head[fr] = cnt - 1;
    e[cnt++] = edge(to, fr, 0, head[to]), head[to] = cnt - 1;
}

int pth[MAXN], dis[MAXN];
bool vis[MAXN];
int s, t;

inline bool bfs() {
    memset(pth, -1, sizeof(pth));
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue <int> q;
    q.push(s);
    vis[s] = 1;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(int i = head[x]; ~i; i = e[i].ne) {
            int y = e[i].to;
            if(e[i].v > 0 && !vis[y]) {
                dis[y] = dis[x] + 1;
                pth[y] = i;
                q.push(y);
                vis[y] = 1;
                
            }
        }
    }
    return ~pth[t];
}

int tim;

inline int get_flow() {
    int minflow = inf;
    int now = pth[t];
    while(~now) {
        minflow = min(minflow, e[now].v);
        now = pth[e[now].fr];
    }
    now = pth[t];
    while(~now) {
        e[now].v -= minflow;
        e[now ^ 1].v += minflow;
        now = pth[e[now].fr];
    }
    
    return minflow;
}

int n, m;

int main() {
    File();
    memset(head, -1, sizeof(head));
    n = get_num();
    m = get_num();
    s = 0;
    t = n + 1;
    for(int i = 1; i <= m; i++) {
        addedge(s, i, 1);
    }
    for(int i = 1; i <= n - m; i++) {
        addedge(i + m, t, 1);
    }
    int t1, t2;
    while(scanf("%d%d", &t1, &t2) == 2) {
        addedge(t1, t2, 1);
    }
    int ans = 0;
    while(bfs()) {
        ans += get_flow();
    }
    printf("%d", ans);

}