UVALive - 7008 Tactical Multiple Defense System——二分图最大匹配

网友投稿 519 2022-11-28

UVALive - 7008 Tactical Multiple Defense System——二分图最大匹配

UVALive - 7008 Tactical Multiple Defense System——二分图最大匹配

一个点由半径和斜率确定，判重后将半径和斜率之间建一条边跑匈牙利即可

#include #include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 2 * 1e4 + 10;int tot, head[maxn];struct Edge { int v, next; Edge(int x = 0, int y = 0) : v(x), next(y) {}}edge[maxn];void init() { tot = 0; memset(head, -1, sizeof(head));}void addedge(int u, int v) { ++tot; edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot;}int n, cnt1, cnt2;map m1;map m2;int from[maxn];bool vis[maxn];bool match(int u) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if (!vis[v]) { vis[v] = true; if (from[v] == -1 || match(from[v])) { from[v] = u; return true; } } } return false;}int hungary() { int ans = 0; memset(from, -1, sizeof(from)); for (int i = 1; i <= cnt1; i++) { memset(vis, false, sizeof(vis)); if (match(i)) ++ans; } return ans;}int main() { int T, r, a, b; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d", &n); init(); cnt1 = 0, cnt2 = 0; m1.clear(); m2.clear(); for (int j = 1; j <= n; j++) { scanf("%d %d %d", &r, &a, &b); if (!m1[r]) m1[r] = ++cnt1; double k = 1.0 * a / b; if (!m2[k]) m2[k] = ++cnt2; addedge(m1[r], m2[k]); } printf("%d\n", hungary()); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

上一篇:PTA 7-7 Windows消息队列
下一篇:HDU 4283 You Are the One ——区间dp
相关文章

 发表评论

暂时没有评论，来抢沙发吧~