「頂点ではなく、辺で考える」という引き出しも持っておこう！
あと、公式解説でsetやiota（連番を生成する関数）などのテクニックが学べる。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <atcoder/all>
#include <set>
#define INF (1LL<<30)
template<class T> inline bool chmin(T& a, T b) {
if (a > b) { a = b; return true; }
else return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) { a = b; return true; }
return false;
}
long long popcount(long long n) {
long long ans = 0;
for (int x = 0; x <= 60; x++) if (((n >> x) & 1) == 1) ans++;
return ans;
}
struct TreeNode {
std::vector<int> Children;
bool IsVisited = false;
};
//int main() {
// int N, Mg, Mh;
// std::cin >> N;
//
// std::cin >> Mg;
// std::vector<TreeNode> G(N, TreeNode());
// for (int i = 0; i < Mg; i++) {
// int u, v;
// std::cin >> u >> v;
// u--; v--;
// G[u].Children.push_back(v);
// G[v].Children.push_back(u);
// }
//
// std::cin >> Mh;
// std::vector<TreeNode> H(N, TreeNode());
// for (int i = 0; i < Mh; i++) {
// int a, b;
// std::cin >> a >> b;
// a--; b--;
// H[a].Children.push_back(b);
// H[b].Children.push_back(a);
// }
//
// std::vector<std::vector<int>> A(N, std::vector<int>(N, 0));
// for (int n = 0; n < (N); n++) {
// for (int j = n + 1; j < (N); j++) {
// std::cin >> A[n][j];
// A[j][n] = A[n][j]; //逆向きのコストも追加しておく！！
// }
// }
//
// std::vector<int> ind;
// for (int n = 0; n < N; n++) ind.push_back(n);
// long long ans = INF;
// do {
// long long tmp = 0;
// for (int n = 0; n < N; n++) {
// if (G[n].Children.size() != H[ind[n]].Children.size()) {
// std::sort(begin(G[n].Children), end(G[n].Children));
// std::sort(begin(H[ind[n]].Children), end(H[ind[n]].Children));
//
// for (int i : G[n].Children) {
// if (std::binary_search(begin(H[ind[n]].Children), end(H[ind[n]].Children), i) == false) {
// tmp += A[ind[n]][i];
// }
// }
//
// for (int i : H[ind[n]].Children) {
// if (std::binary_search(begin(G[n].Children), end(G[n].Children), i) == false) {
// tmp += A[ind[n]][i];
// }
// }
// }
// }
//
// ans = std::min(ans, tmp);
// } while (std::next_permutation(begin(ind), end(ind)));
//
// std::cout << ans << std::endl;
//}
int main() {
int N, Mg, Mh;
std::cin >> N;
std::cin >> Mg;
std::set<std::pair<int,int>> G;
for (int i = 0; i < Mg; i++) {
int u, v;
std::cin >> u >> v;
u--; v--;
G.insert({ u,v });
G.insert({ v,u });
}
std::cin >> Mh;
std::set<std::pair<int,int>> H;
for (int i = 0; i < Mh; i++) {
int a, b;
std::cin >> a >> b;
a--; b--;
H.insert({ a,b });
H.insert({ b,a });
}
std::vector<std::vector<int>> A(N, std::vector<int>(N, 0));
for (int n = 0; n < (N); n++) {
for (int j = n + 1; j < (N); j++) {
std::cin >> A[n][j];
A[j][n] = A[n][j]; //逆向きのコストも追加しておく！！
}
}
std::vector<int> ind;
for (int n = 0; n < N; n++) ind.push_back(n);
long long ans = INF;
do {
long long tmp = 0;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
bool containH = (H.find({ i,j }) != end(H));
bool containG = (G.find({ ind[i],ind[j] }) != end(G));
if (containH != containG) {
tmp += A[i][j];
}
}
}
ans = std::min(ans, tmp);
} while (std::next_permutation(begin(ind), end(ind)));
std::cout << ans << std::endl;
}
コメント