codechef Far Graphs
https://www.codechef.com/problems/TBGRAPH
题意 :
- 给一个简单无向图，要求构造一个序列\(a\)，长度为\(n\)，极差小于等于\(L\)(任意)，使得原图中\(x,y\)相连， 当且仅当\(|a_x-a_y|\ge L/2\)。 要求\(L\le 2e9,ai\)互不相等。
分析:
- 显然\(L\)越大越好
- 如果有奇环，一定是由一个三元环构成的，现在考虑没有奇环的情况。
- 图是一个二分图，不妨把左侧点集放在左边，右侧点集放在右边。
- 分别按度数排序，这样就能确定出\(a_i\)的相对位置关系。
- 然后差分约束一下就可以了，复杂度\(O(n^2)\)。
- 有奇环的情况，先任意求出一个三元环，枚举哪个点是\(L/2\)，将他删掉，判断新图是否为二分图， 然后按二分图那么做，这里可以直接把和\(L\)相连的放在左边，把和\(0\)相连的放在右边。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <bitset>
#include <set>
#include <iostream>
using namespace std;
#define N 1050
#define M 1000050
#define db(x) cerr<<#x<<" = "<<x<<endl
const int inf=1000000000;
int mp[N][N],n,m,vis[N],col[N];
int lp3,a[N],b[N],la,lb,du[N],S;
int head[N],to[M],nxt[M],val[M],inq[N],cnt;
int dis[N],Q[N],dep[N],p1,p2,p3,d[N],FK;
bitset<N>bit[N];
inline void add(int u,int v,int w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
inline bool cmp(int x,int y) {return du[x]<du[y];}
void dfs(int x,int y) {
// printf("x=%d y=%d\n",x,y);
vis[x]=1;
int i;
for(i=1;i<=n;i++) if(mp[x][i]) {
// if(x==6&&i==7) db(col[6]),db(col[7]),db(vis[7]);
if(!vis[i]) d[i]=d[x]+1,col[i]=col[x]^1,dfs(i,x);
}
}
void gun() {
puts("No");
}
bool spfa() {
int i,l=0,r=0;
for(i=1;i<=S;i++) dis[i]=1<<30,inq[i]=0,dep[i]=0;
dis[S]=0;
Q[r++]=S;
while(l!=r) {
int x=Q[l++]; inq[x]=0; if(l==S+1) l=0;
for(i=head[x];i;i=nxt[i]) if(dis[to[i]]>dis[x]+val[i]) {
dep[to[i]]=dep[x]+1;
if(dep[to[i]]>n+1) return 1;
dis[to[i]]=dis[x]+val[i];
if(!inq[to[i]]) {
inq[to[i]]=1;
Q[r++]=to[i];
if(r==S+1) r=0;
}
}
}
return 0;
}
void dfs2(int x) {
int i; vis[x]=1;
for(i=1;i<=n;i++) if(mp[x][i]&&i!=p2) {
if(!vis[i]) col[i]=col[x]^1,dfs2(i);
else if(col[i]==col[x]) {
FK=1;
}
}
}
void solve() {
lp3=0; FK=0;
la=lb=0; p1=p2=p3=0;
scanf("%d%d",&n,&m);
int i,x,y,j,k; S=n+1;
for(i=1;i<=n;i++) du[i]=0,vis[i]=d[i]=0,vis[i]=col[i]=0;
for(i=1;i<=S;i++) head[i]=0; cnt=0;
for(i=1;i<=n;i++) bit[i].reset();
for(i=1;i<=n;i++) for(j=1;j<=n;j++) mp[i][j]=0;
for(i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
mp[x][y]=mp[y][x]=1,du[x]++,du[y]++;
bit[x][y]=bit[y][x]=1;
}
for(i=1;i<=n;i++) if(!vis[i]) d[i]=0,col[i]=0,dfs(i,0);
for(i=1;i<=n&&!p1;i++) for(j=1;j<=n&&!p1;j++) if(i!=j&&mp[i][j]) {
if((bit[i]&bit[j]).count()) {
p1=i,p2=j; lp3=1;
for(k=1;k<=n;k++) if(mp[i][k]&&mp[j][k]) {p3=k; break;}
break;
}
}
if(lp3) {
// printf("%d %d %d\n",p1,p2,p3);
int cas=3,loop=1;
for(;cas--;swap(p1,p2),swap(p2,p3)) {
int i,flg=1;
la=lb=0;
for(i=1;i<=n;i++) vis[i]=0,col[i]=0,d[i]=0;
FK=0;
for(i=1;i<=n;i++) if(!vis[i]&&i!=p2) col[i]=d[i]=0,dfs2(i);
if(FK) continue;
for(i=1;i<=n;i++) if(i!=p1&&i!=p2&&i!=p3) {
if(mp[i][p2]) {
flg=0; break;
}
if(mp[i][p1]&&mp[i][p3]) {flg=0; break;}
if(!mp[i][p1]&&!mp[i][p3]) {flg=0; break;}
if(mp[i][p1]) {
b[++lb]=i;
}else {
a[++la]=i;
}
}
if(!flg) {continue;}
for(i=1;i<=n;i++) du[i]=0;
for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(mp[i][j]&&j!=p1&&j!=p2&&j!=p3) {
du[i]++;
}
sort(a+1,a+la+1,cmp); sort(b+1,b+lb+1,cmp);
for(i=1;i<=S;i++) head[i]=0; cnt=0;
for(i=1;i<=la;i++) {
for(j=lb-du[a[i]]+1;j<=lb;j++) if(!mp[a[i]][b[j]]) {
break;
}
if(j<=du[a[i]]) {gun();return ;}
}
for(i=1;i<=lb;i++) {
for(j=la-du[b[i]]+1;j<=la;j++) if(!mp[b[i]][a[j]]) {
break;
}
if(j<=du[b[i]]) {gun();return ;}
}
add(S,p1,0); add(p1,S,0); add(S,p2,inf/2); add(p2,S,-inf/2); add(S,p3,inf); add(p3,S,-inf);
for(i=1;i<la;i++) add(a[i],a[i+1],-1);
if(la&&lb) add(b[1],a[1],-1);
for(i=lb;i>1;i--) add(b[i],b[i-1],-1);
for(i=1;i<=la;i++) add(S,a[i],inf/2-1);
for(i=1;i<=lb;i++) add(b[i],S,-inf/2-1),add(S,b[i],inf-1);
// for(i=1;i<=la;i++) db(a[i]);
// for(i=1;i<=lb;i++) db(b[i]);
for(i=1;i<=la;i++) {
if(lb-du[a[i]]>=1) add(a[i],b[lb-du[a[i]]],inf/2-1);
else if(la) add(a[i],a[1],inf/2-1);
if(lb-du[a[i]]+1>=1&&lb-du[a[i]]+1<=lb) add(b[lb-du[a[i]]+1],a[i],-inf/2);
}
for(i=1;i<=lb;i++) {
if(la-du[b[i]]>=1) add(a[la-du[b[i]]],b[i],inf/2-1);
else if(lb) add(b[1],b[i],inf/2-1);
if(la-du[b[i]]+1>=1&&la-du[b[i]]+1<=la) add(b[i],a[la-du[b[i]]+1],-inf/2);
}
loop=spfa();
if(loop) continue;
puts("Yes");
printf("%d ",inf);
for(i=1;i<=n;i++) printf("%d ",dis[i]);
puts("");
// return ;
break;
}
if(loop) {gun(); return ;}
}else {
for(i=1;i<=n;i++) {
if(!col[i]) a[++la]=i;
else b[++lb]=i;
}
sort(a+1,a+la+1,cmp);
sort(b+1,b+lb+1,cmp);
// db(la); db(lb);
// for(i=1;i<=la;i++) db(a[i]);
// for(i=1;i<=lb;i++) db(b[i]);
// for(i=1;i<=n;i++) db(du[i]);
for(i=1;i<=la;i++) {
for(j=lb-du[a[i]]+1;j<=lb;j++) if(!mp[a[i]][b[j]]) {
break;
}
if(j<=lb) {gun();return ;}
}
for(i=1;i<=lb;i++) {
for(j=la-du[b[i]]+1;j<=la;j++) if(!mp[b[i]][a[j]]) {
break;
}
if(j<=la) {gun();return ;}
}
for(i=1;i<=n;i++) add(S,i,inf);
for(i=1;i<la;i++) add(a[i],a[i+1],-1);
if(la&&lb) add(b[1],a[1],-1);
for(i=lb;i>1;i--) add(b[i],b[i-1],-1);
for(i=1;i<=la;i++) {
if(lb-du[a[i]]>=1) add(a[i],b[lb-du[a[i]]],inf/2-1);
else if(la) add(a[i],a[1],inf/2-1);
if(lb-du[a[i]]+1>=1&&lb-du[a[i]]+1<=lb) add(b[lb-du[a[i]]+1],a[i],-inf/2);
}
for(i=1;i<=lb;i++) {
if(la-du[b[i]]>=1) add(a[la-du[b[i]]],b[i],inf/2-1);
else if(lb) add(b[1],b[i],inf/2-1);
if(la-du[b[i]]+1>=1&&la-du[b[i]]+1<=la) add(b[i],a[la-du[b[i]]+1],-inf/2);
}
int loop=spfa();
if(loop) {gun(); return ;}
puts("Yes");
printf("%d ",inf);
for(i=1;i<=n;i++) printf("%d ",dis[i]);
puts("");
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) if((abs(dis[i]-dis[j])>=inf/2)^mp[i][j]) puts("FUCK");
}
#include <cmath>
typedef double f2;
int main() {
// f2 a=log(1000000001);
// int i;
// for(i=1;i<=1000000000;i++) a-=1.0/i;
// printf("%.5f\n",a);
// freopen("graph.in","r",stdin);
// freopen("graph.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)solve();
}
/*
3
3 3
1 2
2 3
3 1
7 8
1 6
1 4
3 2
6 3
3 4
4 5
4 7
5 6
4 6
1 2
1 3
1 4
2 3
2 4
3 4
*/