有趣啊~手玩一下這棵樹，發現因為連邊只對相連點的位數有限制，我們可以認為是在往一棵已經有 m 個結點的樹上掛葉子結點直到滿足要求。（m = log(10) n）。注意由于 m 超級無敵小，我們可以直接爆搜初始樹，然后 dinic 二分圖匹配即可。（網絡流：一邊的點表示限制，另一邊的點表示位數。每一條限制可以刪去一個節點， 檢驗一下是否能夠刪完即可）。

#include <bits/stdc++.h> using namespace std; #define maxn 300000 #define INF 9999999 int n, m, cal[maxn], num[maxn], cur[maxn]; int tot, mark[7][7], rec[7][7], lev[maxn]; int S, T, Q[maxn], d[maxn], deg[maxn]; char s1[maxn], s2[maxn]; priority_queue <int, vector <int>, greater <int> > q;int read() {int x = 0, k = 1;char c; c = getchar();while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * k; }struct edge {int cnp, to[maxn], last[maxn], head[maxn], f[maxn], F[maxn];edge() { cnp = 2; }void add(int u, int v, int fl){// cout << "*****" << u << " " << v << " " << fl << endl;to[cnp] = v, f[cnp] = F[cnp] = fl, last[cnp] = head[u], head[u] = cnp ++;to[cnp] = u, f[cnp] = F[cnp] = 0, last[cnp] = head[v], head[v] = cnp ++;} }E1;struct node {int u, v; }id[maxn];bool bfs() {queue <int> q; memset(lev, 0, sizeof(lev)); lev[S] = 1; q.push(S);while(!q.empty()){int u = q.front(); q.pop();for(int i = E1.head[u]; i; i = E1.last[i]){int v = E1.to[i];if(E1.f[i] && !lev[v]){lev[v] = lev[u] + 1;q.push(v);}}if(lev[T]) return 1;}return 0; }int dfs(int u, int nf) {if(u == T || !nf) return nf;int tf = 0;for(int i = E1.head[u]; i; i = E1.last[i]){int v = E1.to[i]; if(!E1.f[i] || lev[v] != lev[u] + 1) continue;int af = dfs(v, min(E1.f[i], nf));tf += af, nf -= af;E1.f[i] -= af, E1.f[i ^ 1] += af;}return tf; }int dinic() {int nf = 0;while(bfs()) nf += dfs(S, INF);return nf; }void dfs2(int u) {for(int i = E1.head[u]; i; i = E1.last[i]){int v = E1.to[i]; if(!E1.f[i ^ 1]) continue;if(u > m && u <= tot + m && v >= 1 && v <= m) for(int j = 1; j <= E1.f[i ^ 1]; j ++){int t = u - m; t = (id[t].u == v) ? id[t].v : id[t].u;printf("%d %d\n", num[t], cur[v] ++);}if(u == S) dfs2(v);} }void Search(int now) {if(now >= m - 1){int t = 1;for(int i = 1; i <= m; i ++) d[i] = deg[i];for(int i = 1; i <= m; i ++) if(!d[i]) q.push(i);memset(mark, 0, sizeof(mark));while(!q.empty() && t <= m - 2){int u = q.top(); q.pop();int x = u, y = Q[t]; if(x > y) swap(x, y);mark[x][y] = 1; d[Q[t]] --;if(!d[Q[t]]) q.push(Q[t]); t ++;}if(q.size() >= 2){int x = q.top(); q.pop(); int y = q.top(); q.pop();mark[x][y] = 1;}else if(q.size() >= 1) q.pop();for(int i = 2; i < E1.cnp; i ++) E1.f[i] = E1.F[i];for(int i = E1.head[S]; i; i = E1.last[i]){int v = E1.to[i]; if(!v) continue; v -= m;int x = id[v].u, y = id[v].v;if(x > y) swap(x, y);E1.f[i] -= mark[x][y]; if(E1.f[i] < 0) return;}if(dinic() == n - m) {for(int i = 1; i <= m; i ++)for(int j = i + 1; j <= m; j ++)if(mark[i][j]) printf("%d %d\n", num[i], num[j]);for(int i = 1; i <= m; i ++) cur[i] ++;dfs2(S);exit(0);}return;}for(int i = 1; i <= m; i ++) deg[i] ++, Q[now] = i, Search(now + 1), deg[i] --; }int main() {n = read(); int t = n;while(t) { m ++; t /= 10; }for(int i = 1, l = 1; i <= m; l *= 10, i ++) num[i] = cur[i] = l;for(int i = 1, l = 1; i < m; l *= 10, i ++) cal[i] = l * 10 - num[i]; cal[m] = n - num[m] + 1; S = 0, T = m * m + m + 3;for(int i = 1; i < n; i ++){scanf("%s%s", s1 + 1, s2 + 1);int l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);if(l1 > l2) swap(l1, l2); rec[l1][l2] ++;}for(int i = 1; i <= m; i ++)for(int j = i; j <= m; j ++){id[++ tot].u = i, id[tot].v = j;E1.add(S, tot + m, rec[i][j]);E1.add(tot + m, i, INF); E1.add(tot + m, j, INF);}for(int i = 1; i <= m; i ++) E1.add(i, T, cal[i] - 1);Search(1);printf("-1\n");return 0; }

?

轉載于:https://www.cnblogs.com/twilight-sx/p/9960810.html

總結

以上是生活随笔為你收集整理的【题解】CF#611 H-New Year and Forgotten Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。