Submission #2312653

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Tapris;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int V, E, V_emb, E_emb, rtV_emb;
map<int, int> G[555];
vector<int> G_emb[3666];
int cent;

int f[555]; // f: V -> V_emb
int g[3666]; // g: V_emb -> V

int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};

void input() {
  cin >> V >> E;
  rep(i, E) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    G[u][v] = G[v][u] = w;
  }

  cin >> V_emb >> E_emb;
  rep(i, E_emb) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    G_emb[a].push_back(b);
    G_emb[b].push_back(a);
  }

  rtV_emb = sqrt(V_emb);

  cent = (rtV_emb%2 ? V_emb/2 : V_emb/2 - rtV_emb/2);

  srand((unsigned)time(NULL));
}

int pos2id(int x, int y) {
  return y*rtV_emb + x;
}

tuple<int, int> id2pos(int id) {
  return make_tuple(id%rtV_emb, id/rtV_emb);
}

bool in(int x, int y) {
  return 0<=x&&x<rtV_emb&&0<=y&&y<rtV_emb;
}

bool in(int a) {
  int x, y; tie(x, y) = id2pos(a);
  return in(x, y);
}

void initMap() {
  memset(f, -1, sizeof(f));
  memset(g, -1, sizeof(g));
  vector<Pi> score_table(V_emb, Pi(-1, -1));
  int ini = rand()%V_emb;
  score_table[ini] = Pi(0, 0);
  int cnt = 0;
  int hoge = 0;
  int piyo = 0;
  while(cnt < V) {
    queue<int> que;
    int idx = -1, pos = -1, max_score = -1;
    rep(i, V_emb) {
      if(~g[i]) continue;
      int v = score_table[i].second, score = score_table[i].first;
      if(v == -1) continue;
      if(~f[v]) continue;
      if(max_score < score) idx = v, pos = i, max_score = score;
    }
    if(idx == -1) {
      while(~f[hoge]) hoge++;
      idx = hoge;
    }
    if(pos == -1) {
      while(~g[piyo]) piyo++;
      pos = piyo;
    }
    f[idx] = pos;
    g[pos] = idx;
    que.push(idx);
    cnt++;
    while(!que.empty() && cnt < V) {
      int curr = que.front(); que.pop();
      for(auto&& p : G[curr]) {
    	int adj = p.first;
    	if(~f[adj]) continue;
    	for(auto&& neighbor : G_emb[f[curr]]) {
    	  if(~g[neighbor]) continue;
    	  int tmp = 0;
    	  for(auto&& nneighbor : G_emb[neighbor]) {
    	    if(g[nneighbor] == -1) continue;
    	    tmp += G[adj][g[nneighbor]];
    	  }
    	  if(~f[score_table[neighbor].second]) {
    	    score_table[neighbor] = Pi(tmp, adj);
    	  } else {
    	    chmax(score_table[neighbor], Pi(tmp, adj));
    	  }
    	}
      }
      int next = -1, f_next = -1, max_score = -1;
      rep(i, V_emb) {
    	if(~g[i]) continue;
    	int v = score_table[i].second, score = score_table[i].first;
    	if(v == -1) continue;
    	if(~f[v]) continue;
    	if(max_score < score) next = v, f_next = i, max_score = score;
      }
      if(~next) {
    	f[next] = f_next;
    	g[f_next] = next;
    	que.push(next);
    	cnt++;
      }
    }
  }
}

int calcGlobalScore() {
  int score = 0;
  rep(v, V) {
    for(auto&& neighbor : G_emb[f[v]]) {
      if(g[neighbor] == -1) continue;
      if(v < g[neighbor] && G[v].count(g[neighbor])) score += G[v][g[neighbor]];
    }
  }
  return score;
}

int calcLocalScore(int id) {
  if(g[id] == -1) return 0;
  int score = 0;
  for(auto&& neighbor : G_emb[id]) {
    if(g[neighbor] == -1) continue;
    if(G[g[id]].count(g[neighbor])) score += G[g[id]][g[neighbor]];
  }
  return score;
}

void solve() {
  initMap();
  int curr_score = calcGlobalScore();
  rep(t, 1000) {
    int swap_v = -1, swap_neighbor = -1, next_score = -1;
    rep(v, V) {
      int dec = calcLocalScore(f[v]);
      int f_v = f[v];
      for(auto&& neighbor : G_emb[f[v]]) {
    	int g_neighbor = g[neighbor];
	int dec2 = calcLocalScore(neighbor);
    	if(~g_neighbor) {
    	  swap(g[f_v], g[neighbor]);
    	  swap(f[v], f[g_neighbor]);
    	} else {
    	  g[f_v] = -1;
    	  g[neighbor] = v;
    	  f[v] = neighbor;
    	}
    	int inc = calcLocalScore(f[v]) + calcLocalScore(neighbor);
    	if(next_score < curr_score-dec-dec2+inc) {
    	  next_score = curr_score-dec-dec2+inc;
    	  swap_v = v;
    	  swap_neighbor = neighbor;
    	}
    	if(~g_neighbor) {
    	  swap(f[v], f[g_neighbor]);
    	  swap(g[f_v], g[neighbor]);
    	} else {
    	  f[v] = f_v;
    	  g[neighbor] = -1;
    	  g[f_v] = v;
    	}
      }
    }
    if(curr_score < next_score) {
      if(~g[swap_neighbor]) {
    	int g_neighbor = g[swap_neighbor];
    	swap(g[f[swap_v]], g[swap_neighbor]);
    	swap(f[swap_v], f[g_neighbor]);
      } else {
    	g[f[swap_v]] = -1;
    	g[swap_neighbor] = swap_v;
    	f[swap_v] = swap_neighbor;
      }
      curr_score = next_score;
    } else {
      break;
    }
  }
  rep(v, V) {
    cout << v+1 << " " << f[v]+1 << endl;
  }
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  input();

  solve();

  return 0;
}

Submission Info

Judge Result