「SCOI2010」连续攻击游戏

传送门

Luogu

解题思路

二分图匹配，关键是建图。

如果我们naive地直接把每个武器的两个属性分为两部建图的话，显然是跑不了的。

我们考虑把每一个武器的属性向它连边：\(a_i \rightarrow i,b_i \rightarrow i\)

然后我们从属性这一部从小到大枚举，寻找增广路，直到找不到就输出答案。

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= c == '-', c = getchar();

	while (isdigit(c)) s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 10010;

const int __ = 1000010;

int tot, head[_], nxt[__ << 1], ver[__ << 1];

inline void Add_edge(int u, int v)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }

int vis[__], bel[__];

inline int dfs(int u) {

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i];

		if (vis[v]) continue; vis[v] = 1;

		if (!bel[v]) return bel[v] = u, 1;

		else if (dfs(bel[v])) return bel[v] = u, 1;

	}

	return 0;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	int n; read(n);

	for (rg int a, b, i = 1; i <= n; ++i)

		read(a), read(b), Add_edge(a, i), Add_edge(b, i);

	int ans = 0;

	for (rg int i = 1; i <= 10000; ++i) {

		memset(vis, 0, sizeof (int) * (n + 1));

		if (dfs(i)) ++ans; else break;

	}

	printf("%d\n", ans);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「SCOI2010」连续攻击游戏

解题思路

细节注意事项

参考代码

最新文章

热门文章