美团CodeM2018资格赛赛题官方版本详解（六）——匹配

快来打我* 2022-05-22 02:07 191阅读 0赞

![20180612215845794][]![20180612215858615][]

**解题思路**

![20180612215908933][]![20180612215920590][]![20180612215931865][]

**标准程序**

#include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <vector>
    #include <bitset>
    #include <cmath>
    #include <ctime>
    #include <queue>
    #include <set>
    #include <map>
    #define fi first
    #define se second
    #define PA pair<int,int>
    #define VI vector<int>
    #define VP vector<PA >
    #define mk(x,y) make_pair(x,y)
    #define int64 long long
    #define db double
    #define N 1010
    #define M 100010
    #define For(i,x,y) for (i=x;i<=y;i++)
    using namespace std;
    struct ww {
    	int a, b, c;
    } a[M];
    int i, j, k, n, m, t, ans, T;
    int b[N], c[N], d[N], pre[N];
    bool Rea[N];
    VI e[N];
    
    inline bool cc1(const ww &a, const ww &b) {
    	return a.c < b.c;
    }
    
    void dfs1(int x) {
    	if (!x || Rea[x]) return;
    	Rea[x] = 1;
    	int i;
    	for (i = 0; i < e[x].size(); i++) {
    		int A = e[x][i];
    		if (!pre[A]) pre[A] = x;
    		dfs1(d[A]);
    	}
    }
    inline void Pre() {
    	memset(Rea, 0, sizeof(Rea));
    	memset(pre, 0, sizeof(pre));
    	int i;
    	For(i, 1, n) if (!c[i]) dfs1(i);
    }
    int dfs(int x, int y) {
    	if (Rea[x]) return 0;
    	Rea[x] = 1;
    	int i;
    	for (i = y; i < e[x].size(); i++) {
    		int A = e[x][i];
    		if (!pre[A]) pre[A] = x;
    		if (!d[A] || dfs(d[A], 0)) {
    			c[x] = A;
    			d[A] = x;
    			return 1;
    		}
    	}
    	return 0;
    }
    void Dfs(int x) {
    	if (!x) return;
    	int A = pre[x];
    	int B = c[A];
    	c[A] = x;
    	d[x] = A;
    	Dfs(B);
    }
    inline void Add(ww b) {
    	int x = b.a, y = b.b;
    	e[x].push_back(y);
    	if (Rea[x]) {
    		Rea[x] = 0;
    		int z = c[x];
    		if (dfs(x, e[x].size() - 1)) {
    			ans++;
    			Dfs(z);
    			Pre();
    		}
    	}
    }
    int main() {
    	scanf("%d%d", &n, &m);
    	t = 0;
    	For(i, 1, m) {
    		int x, y, z;
    		scanf("%d%d%d", &x, &y, &z);
    		a[++t] = (ww){x, y, z};
    	}
    	sort(a+1, a+t+1, cc1);
    	memset(b, 255, sizeof(b));
    	memset(c, 0, sizeof(c));
    	memset(d, 0, sizeof(d));
    	For(i, 1, n) e[i].clear();
    	Pre();
    	ans = 0;
    	For(i, 1, t) {
    		Add(a[i]);
    		if (b[ans] < 0) b[ans] = a[i].c;
    		if (ans == n) break;
    	}
    	For(i, 1, n) printf("%d%c", b[i], i == n ? '\n' : ' ');
    	return 0;
    }

[20180612215845794]: https://img-blog.csdn.net/20180612215845794
[20180612215858615]: /images/20220522/8e55a2a81a274a1392a785b172caa234.png
[20180612215908933]: https://img-blog.csdn.net/20180612215908933
[20180612215920590]: https://img-blog.csdn.net/20180612215920590
[20180612215931865]: /images/20220522/a2d29683c0434cc4b42c95ace7eaa79f.png