首页 > 代码库 > UVa818 Cutting Chains (二进制枚举)
UVa818 Cutting Chains (二进制枚举)
链接：http://vjudge.net/problem/35523
分析：links记录初始圆环链的情况，然后二进制枚举编号为0~n-1的圆环哪个被打开了，一个圆环最多一个前驱和一个后继，所以judge判断如果有一个未打开的圆环同时和2个以上的未打开圆环相连就一定不能形成链，剪去。circle判断剩下的未打开圆环是否形成环，以及若未成环那么有多少条单链links_num，注意最后成链不用按顺序比如1->2->3...这样。然后判断一下打开的圆环数够不够把links_num条单链扣成一条链，若能，则更新ans，最后枚举完所有情况则可以得到最少的打开圆环数，打印输出。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 20; 7 8 int n, links_num, ans, links[maxn][maxn], vis[maxn]; 9 10 void init() {11 ans = 0x3f3f3f3f;12 memset(links, 0, sizeof(links));13 int u, v;14 while (scanf("%d%d", &u, &v) == 2 && u != -1) {15 links[u - 1][v - 1] = 1;16 links[v - 1][u - 1] = 1;17 }18 }19 20 bool judge(int s) {21 for (int i = 0; i < n; i++) {22 if (s & (1 << i)) continue;23 int cnt = 0;24 for (int j = 0; j < n; j++) {25 if (s & (1 << j)) continue;26 if (links[i][j]) cnt++;27 }28 if (cnt > 2) return true;29 }30 return false;31 }32 33 bool dfs(int now, int fa, int s) {34 vis[now] = 1;35 for (int i = 0; i < n; i++) {36 if (!links[now][i] || (s & (1 << i)) || i == fa) continue;37 if (vis[i]) return true;38 if (dfs(i, now, s)) return true;39 }40 return false;41 }42 43 bool circle(int s) {44 for (int i = 0; i < n; i++) {45 if (vis[i] || (s & (1 << i))) continue;46 links_num++;47 if (dfs(i, -1, s)) return true;48 }49 return false;50 }51 52 int cal(int s) {53 return s == 0 ? 0 : cal(s / 2) + (s & 1);54 }55 56 void solve() {57 for (int i = 0; i < (1 << n); i++) {58 links_num = 0; memset(vis, 0, sizeof(vis));59 if (judge(i) || circle(i)) continue;60 if (cal(i) >= links_num - 1) ans = min(ans, cal(i));61 }62 }63 64 int main() {65 int kase = 0;66 while (scanf("%d", &n) == 1 && n) {67 init();68 solve();69 printf("Set %d: Minimum links to open is %d\n", ++kase, ans);70 }71 return 0;72 }
UVa818 Cutting Chains (二进制枚举)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。