問題:http://judge.imoz.jp/page.php?page=view_problem&pid=63&cid=12
解説が上がってたので読みながらコードを書いてみた.
とりあえずクラスカル法を使って部分点(N<=10)がとれるコードだけ書けた.いやまあ通る全パターン使ってるからだと思うけど.通らないほうが10個以下なのでこっちを考慮すれば何も問題ないけど力不足で書けない.なのでいつかまた書く.
import java.util.*; // C "Connect The Decoration" public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); for (int n, m; (n = s.nextInt()) + (m = s.nextInt()) > 0;) { Kruskal kruskal = new Kruskal(n); boolean[] b = new boolean[n]; for (int i = 0; i < n; ++i) { b[i] = s.nextInt() < 1; } for(int i = 0; i < m ;++i){ int u = s.nextInt()-1, v = s.nextInt()-1, cost = s.nextInt(); kruskal.addEdge(u, v, cost); kruskal.addEdge(v, u, cost); } kruskal.init(); int result = Integer.MAX_VALUE; for(int i = 1; i < 1 << n; ++i){ if(!f(i, b)){ continue; } List<int[]> edges = kruskal.getEdges(i); if(edges.size() != Long.bitCount(i)-1){ continue; } int r = 0; for(int[] edge: edges){ r += edge[2]; } result = Math.min(result, r); } System.out.println(result); } } private static boolean f(int i, boolean[] b){ for(int j = 0; j < b.length; ++j){ if(b[j] && (i&1<<j)<1){ return false; } } return true; } static class Kruskal { int n; List<int[]> edges; public Kruskal(int n) { this.n = n; edges = new ArrayList<int[]>(); } void addEdge(int u, int v, int cost) { edges.add(new int[] { u, v, cost }); } void init() { Collections.sort(edges, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[2] - o2[2]; } }); } List<int[]> getEdges(int b) { UnionFind uf = new UnionFind(n); List<int[]> result = new ArrayList<int[]>(); for (int[] edge : edges) { if ((b & 1 << edge[0]) > 0 && (b & 1 << edge[1]) > 0 && !uf.isSame(edge[0], edge[1])) { uf.unite(edge[0], edge[1]); result.add(edge); } } return result; } } static class UnionFind { int[] par; int[] rank; public UnionFind(int n) { par = new int[n]; rank = new int[n]; for (int i = 0; i < n; ++i) { par[i] = i; rank[i] = 0; } } int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) ++rank[x]; } } boolean isSame(int x, int y) { return find(x) == find(y); } } }
※追記
できた.使わないかもしれない頂点を低い数字にマッピングして,使わないかもしれない頂点個のビットによって通る通らないという判定を行って,通ることになる頂点だkをつかって最小被覆木を求めた.
import java.util.*; // C "Connect The Decoration" public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); for (int n, m; (n = s.nextInt()) + (m = s.nextInt()) > 0;) { Kruskal kruskal = new Kruskal(n); int unusedMax = 0; int[] a = new int[n]; int x = 0, y = n - 1; for (int i = 0; i < n; ++i) { if(s.nextInt() > 0){ ++unusedMax; a[i] = x++; }else{ a[i] = y--; } } for(int i = 0; i < m ;++i){ int u = s.nextInt()-1, v = s.nextInt()-1, cost = s.nextInt(); kruskal.addEdge(a[u], a[v], cost); kruskal.addEdge(a[v], a[u], cost); } kruskal.init(unusedMax); int result = Integer.MAX_VALUE; for(int i = 0; i < 1 << unusedMax; ++i){ List<int[]> edges = kruskal.getEdges(i); if(edges.size() != n - Integer.bitCount(i) - 1){ continue; } int r = 0; for(int[] edge: edges){ r += edge[2]; } result = Math.min(result, r); } System.out.println(result); } } static class Kruskal { int n; List<int[]> edges; int unusedMax; public Kruskal(int n) { this.n = n; edges = new ArrayList<int[]>(); } void addEdge(int u, int v, int cost) { edges.add(new int[] { u, v, cost }); } void init(int unusedMax) { this.unusedMax = unusedMax; Collections.sort(edges, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[2] - o2[2]; } }); } List<int[]> getEdges(int b) { UnionFind uf = new UnionFind(n); List<int[]> result = new ArrayList<int[]>(); for (int[] edge : edges) { if (!(edge[0] < unusedMax && !((b & 1 << edge[0]) < 1)) && !(edge[1] < unusedMax && !((b & 1 << edge[1]) < 1)) && !uf.isSame(edge[0], edge[1])) { uf.unite(edge[0], edge[1]); result.add(edge); } } return result; } } static class UnionFind { int[] par; int[] rank; public UnionFind(int n) { par = new int[n]; rank = new int[n]; for (int i = 0; i < n; ++i) { par[i] = i; rank[i] = 0; } } int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) ++rank[x]; } } boolean isSame(int x, int y) { return find(x) == find(y); } } }