ABC371-C Make Isomorphic 解説

なんとなく書いてみます

問題概要

Hのグラフの辺を削除、追加してGとHを同じ形にする
グラフは番号を並び替えていいらしい
頂点にくっついている辺の番号が同じであればいい

考察

並び替えていいなら順列を考えて見る。頂点の数が８なので計算量はほぼ考えなくて良さそう
Hの頂点の番号を並び替えてGにあって、Hにない辺とGになくて、Hにある辺を見つけてその分のお金を足していく。この流れを番号を並び替えて何回もやってその中でお金が少ないものを出せば良さそう

実装

入力を受け取る

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define oke cout << "Yes" << '\n';
#define dame cout << "No" << '\n';
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using HaiI = vector<vector<int>>;
using Hai2 = vector<vector<ll>>;
using HaiB = vector<vector<bool>>;
using Hai3 = vector<vector<vector<ll>>>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	ll N,GM,GH;
	cin>>N>>GM;
	Hai2 G(N);
	rep(i,GM){
	  int a,b;
	  cin>>a>>b;
	  a--,b--;
	  G[a].push_back(b);
	  G[b].push_back(a);
	}
	
	Hai2 H(N);
	cin>>GH;
	rep(i,GH){
	  int a,b;
	  cin>>a>>b;
	  a--,b--;
	  H[a].push_back(b);
	  H[b].push_back(a);
	}
	
	Hai2 A(N,vector<ll>(N));
	for(int i=0;i<N-1;i++){
	  for(int j=i+1;j<N;j++){
	    cin>>A[i][j];
        //ここ解説します
	    A[j][i]=A[i][j];
	  }
	}
}

Aの入力はi>jのお金しか入力がありません
総当たり表の右上しか埋まってないイメージです。なので左下も埋めていきます

順列を作る

    ll ans=1e15;
	vector<int>S(N);
	rep(i,N){
	  S[i]=i;
	}
	do{
    
	}while(next_permutation(all(S)));
    //all(S)はS.begin(),S.end()
    cout<<ans<<endl;
}

Hをそのまま順列に入れることはできないと思うので、Sで添字を調整するように作っています
A[i]のところをA[S[i]]にする感じです

ここで詰まる
GとHの辺を見つけることができない。Gの辺を全部探索してHと被ってない所を見つけてお金を足そうとしたがHにあってGに無い辺を見つけられない。

1~N（添字だと0~N-1）まで全部で見て頂点iから頂点jの辺があるか、無いかを判断したい。
よって、グラフをsetで入力をもらうことにした。

	ll N,GM,GH;
	cin>>N>>GM;
	vector<set<int>>G(N);
	rep(i,GM){
	  int a,b;
	  cin>>a>>b;
	  a--,b--;
	  G[a].insert(b);
	  G[b].insert(a);
	}
	
	vector<set<int>>H(N);
	cin>>GH;
	rep(i,GH){
	  int a,b;
	  cin>>a>>b;
	  a--,b--;
	  H[a].insert(b);
	  H[b].insert(a);
	}
}    

そしてG[i].count(j)でGの頂点iから頂点jに辺があるかを確認できる。

    do{
	  ll cost=0;
	  set<pair<int,int>>L;
	  rep(i,N){
	    for(int j=0;j<i;j++){
	      if(G[i].count(j) != H[S[i]].count(S[j])){
	        cost+=A[S[i]][S[j]];
	      }
	    }
	  }
	  ans=min(ans,cost);
	}while(next_permutation(all(S)));

S[i]で並び替えたHのグラフを表すことができる。
GではなくHのグラフの辺を追加、削除するのでお金もA[i][j]ではなくA[S[i]][S[j]]となる
これで辺を確認してお金を足すことができた。
コード全文

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define oke cout << "Yes" << '\n';
#define dame cout << "No" << '\n';
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using HaiI = vector<vector<int>>;
using Hai2 = vector<vector<ll>>;
using HaiB = vector<vector<bool>>;
using Hai3 = vector<vector<vector<ll>>>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	ll N,GM,GH;
	cin>>N>>GM;
	vector<set<int>>G(N);
	rep(i,GM){
	  int a,b;
	  cin>>a>>b;
	  a--,b--;
	  G[a].insert(b);
	  G[b].insert(a);
	}
	
	vector<set<int>>H(N);
	cin>>GH;
	rep(i,GH){
	  int a,b;
	  cin>>a>>b;
	  a--,b--;
	  H[a].insert(b);
	  H[b].insert(a);
	}
	
	Hai2 A(N,vector<ll>(N));
	for(int i=0;i<N-1;i++){
	  for(int j=i+1;j<N;j++){
	    cin>>A[i][j];
	    A[j][i]=A[i][j];
	  }
	}
	
	ll ans=1e15;
	vector<int>S(N);
	rep(i,N){
	  S[i]=i;
	}
	do{
	  ll cost=0;
	  set<pair<int,int>>L;
	  rep(i,N){
	    for(int j=0;j<i;j++){
	      if(G[i].count(j) != H[S[i]].count(S[j])){
	        cost+=A[S[i]][S[j]];
	      }
	    }
	  }
	  ans=min(ans,cost);
	}while(next_permutation(all(S)));
	cout<<ans<<endl;
}

AC!