首页 > 代码库 > UVA 11330 - Andy's Shoes(置换分解)
UVA 11330 - Andy's Shoes(置换分解)
UVA 11330 - Andy‘s Shoes
题目链接
题意:andy有很多双鞋子,每双鞋子有一个编号,现在他把鞋子左右左右放回去,可是不能保证所有鞋子左边和右边是同一编号,现在要求用最少的交换次数,使得所有鞋子左右编号相同
思路:置换的分解,固定左边的鞋子,这样右边的鞋子就可以看成是放在哪个位置,然后根据这个求出每个循环的长度,最后每个循环长度-1的总和就是答案
代码:
#include <cstdio> #include <cstring> int t, n, vis[10005]; int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); int l, r; for (int i = 0; i < n; i++) { scanf("%d%d", &l, &r); vis[l] = r; } int ans = 0; for (int i = 1; i <= 10000; i++) { if (vis[i]) { int cnt = 0; int now = vis[i]; vis[i] = 0; while (vis[now]) { cnt++; int tmp = vis[now]; vis[now] = 0; now = tmp; } ans += cnt; } } printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。