(Un)labeled graphs 题解
orz jiangly
通信题。不禁让人想到。
对于这道题目,考虑要还原原来的点的编号,而题目条件里有一个 。
还是非常明显,发现我们可以搞出一排新的点让它们构成一条新的链。然后第 \(i\) 个点往原图中编号为 \(u\) 的点连边,满足 \(u \& 2^{i-1}\)。
现在我们需要解决的问题是如何辨认出这条链。发现还多了三个点可以供我们操作。设其为 A,B,C。
考虑怎么搞出一个特殊点让我们一开始就可以辨认出来。令其度数最大即可。于是我们让 A 与其他所有点连边。这样就可以把它一眼顶真出来。
发现好像只知道这一个点有点废。于是我们钦定 C 是唯一一个不与 A 连的点。然后我们又得到了一个可以被识别出来的全新点。
延续之前的思路,之前是向所有点连边,考虑让 C 只和一些点连边。比方说,让 C 与 B 连边,我们又得到了 B。
先考虑识别出链来,于是我们让 B 向原图中的所有点连边。这样不与 B 连边的点就是链上的点了。
发现无法确定链的方向。于是我们让 C 与链的端点连边。怎么区分链端点和 B ?看度数即可。
// Problem: C - (Un)labeled graphs
// URL: https://vjudge.net/contest/643391#problem/C
// Written by WRuperD
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 3e3 + 10;
bool edge[MAX][MAX];
void work2(int n, int m){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
char ch = getchar();
while(ch != '0' and ch != '1') ch = getchar();
edge[i][j] = ch - '0';
}
}
for(int i = n + 1; i <= m - 3; i++){
int now = i - n - 1;
for(int j = 1; j <= n; j++){
if(j & (1ll << now)){
edge[j][i] = edge[i][j] = 1;
}
}
if(i != m - 3){
edge[i][i + 1] = edge[i + 1][i] = 1;
}
}
int A = m - 2, B = m - 1, C = m;
for(int i = 1; i < m; i++) {
if(i != A) edge[i][A] = edge[A][i] = 1;
}
edge[B][C] = edge[C][B] = 1;
edge[n + 1][C] = edge[C][n + 1] = 1;
for(int i = 1; i <= n; i++){
edge[B][i] = edge[i][B] = 1;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
write(edge[i][j]);
}endl;
}
}
int id[MAX];
int deg[MAX];
int Ans[MAX][MAX];
bool isg[MAX];
void work(int x, int nowid, int m){
for(int i = 1; i <= m; i++){
if(edge[x][i] and isg[i]){
id[i] |= nowid;
}
}
id[x] = inf;
isg[x] = 1;
for(int i = 1; i <= m; i++) if(edge[x][i] and !isg[i]) work(i, nowid * 2, m);
}
void work3(int m, int n){
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
char ch = getchar();
while(ch != '0' and ch != '1') ch = getchar();
edge[i][j] = ch - '0';
deg[i] += edge[i][j], deg[j] += edge[i][j];
}
}
int A = 0;
for(int i = 1; i <= m; i++){
if(deg[A] < deg[i]) A = i;
}
id[A] = n + 1;
int C = 0;
for(int i = 1; i <= m; i++) if(i != A and edge[A][i] == 0) C = i;
int B = 0;
for(int i = 1; i <= m; i++) if(edge[C][i] and deg[i] >= deg[B]) B = i;
for(int i = 1; i <= m; i++) if(edge[B][i] and i != A and i != C) isg[i] = 1;
id[A] = id[B] = id[C] = inf;
isg[A] = isg[B] = isg[C] = 1;
// write(A), put(), write(B), put(), write(C), endl;
for(int i = 1; i <= m; i++) if(edge[C][i] and i != B) work(i, 1, m);
// write(isg[2]), endl;
for(int i = 1; i <= m; i++) if(!id[i]) id[i] = n;
// for(int i = 1; i <= m; i++) write(is[])
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
if(!id[i] or !id[j] or id[i] > n or id[j] > n or i == A or i == B or i == C or j == A or j == B or j == C) continue;
Ans[id[i]][id[j]] = edge[i][j];
Ans[id[j]][id[i]] = edge[i][j];
}
}
// for(int i = 1; i <= m; i++) if()
// write(A), put(), write(B), put(), write(C), endl;
// for(int i = 1; i <= m; i++) write(id[i]), put();
// endl;
// write(n), endl;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
write(Ans[i][j]);
}endl;
}
}
void solve(){
int n = read(), m = read();
if(n < m) work2(n, m);
else work3(n, m);
}
signed main(){
int t = 1;
while(t--) solve();
return 0;
标签:ch,点连边,int,solution,long,qoj8794,id,define
From: https://www.cnblogs.com/WRuperD/p/18323944