作者存档：edward_mj

【题目地址】http://evaluator.hsin.hr/login.php?redirect=index.php
【题目大意】
一个N,E<=10^5的无向图
每条边可以染黑白两色。
求一个染色方案，使每一个度>1的点，都拥有与之相连的黑边和白边。
【算法分析】
。。。我只会骗分了，应该还可以写个随机调整搞一下。
我是把它当树来走，树边染上dep[p] mod 2+1的颜色。
然后其他边如果只有某一边需要，那么就完成那一边的需求。
否则随便完成某一边的需求。
【数据通过情况】
Test # Score Time Memory Result 1 0.0 0.00s 6956 kB You program printed 0, but there is a valid solution. 2 6.5 0.00s 6956 kB Correct! 3 6.5 0.00s 6956 kB Correct! 4 0.0 0.00s 6956 kB You program printed 0, but there is a valid solution. 5 0.0 0.00s 6956 kB Correct! 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.00s 6956 kB Correct! 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.00s 6956 kB Correct! 0.00s 6956 kB Correct! 6 0.0 0.11s 10000 kB Correct! 0.09s 6956 kB Correct! 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.11s 10000 kB You program printed 0, but there is a valid solution. 0.10s 7916 kB You program printed 0, but there is a valid solution. 0.11s 8592 kB You program printed 0, but there is a valid solution. 0.11s 7720 kB Correct! 0.10s 8248 kB You program printed 0, but there is a valid solution.
显然。。。因为它搞到多组测试数据，完全没办法得很多分。。。但是过的点也不少了。。。
求正解
【CODE】
#include #include #include const int N=105555;
struct edge{int x,y,color,next,op;}g[N*2];
int n,e;
int ls[N],dep[N],du[N],donec[N],fa[N];

inline void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
g[++e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}

void init(){
int i,x,y,m;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
du[x]++; du[y]++;
}
}

inline void draw(int t,int co){
if (g[t].color) return;
if (co==3 || co==1){
g[t].color=1;
g[g[t].op].color=1;
}
else{
g[t].color=2;
g[g[t].op].color=2;
}
if (!donec[g[t].x]) donec[g[t].x]=co;
if (donec[g[t].x]!=co) donec[g[t].x]=3;
if (!donec[g[t].y]) donec[g[t].y]=co;
if (donec[g[t].y]!=co) donec[g[t].y]=3;
}

void dfs(int p){
for (int t=ls[p];t;t=g[t].next)
if (!dep[g[t].y]){
dep[g[t].y]=dep[p]+1;
fa[g[t].y]=t;
draw(t,dep[p]%2+1);
dfs(g[t].y);
}
else if (g[t].op!=fa[p]){
if (donec[g[t].y]==3) draw(t,3-donec[p]);
else if (donec[g[t].y]==donec[p]) draw(t,3-donec[p]);
else draw(t,donec[p]);
}
}

void work(){
int i;
for (i=1;i<=n;i++)
if (!dep[i]){
dep[i]=1;
dfs(i);
}
}

void update(int p){
donec[p]=0;
for (int t=ls[p];t;t=g[t].next){
if (!donec[p]) donec[p]=g[t].color;
if (donec[p]!=g[t].color) {donec[p]=3; return;}
}
}

bool Try_opc(int ss){
for (int t=ls[g[ss].x];t;t=g[t].next)
if (g[t].color==g[ss].color && t!=ss){
g[ss].color=3-g[ss].color;
g[g[ss].op].color=g[ss].color;
donec[g[ss].x]=3;
update(g[ss].y);
return true;
}
return false;
}

void solve(){
bool flag=true;
for (int i=1;i<=n;i++)
for (int t=ls[i];t && du[i]>1 && donec[i]!=3;t=g[t].next)
if (Try_opc(t)) break;
for (int i=1;i<=n;i++)
if (du[i]>1 && donec[i]!=3){
flag=false;
}
if (!flag){
printf("0n");
return;
}
for (int i=1;i printf("%dn",g[i].color);
}

int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
init();
work();
solve();
}

【题目地址】http://evaluator.hsin.hr/login.php?redirect=index.php
【题目大意】
给定N<=10^5个点，每个点有一个三维坐标(Xi,Yi,Zi)
两个点间的距离定义为Distance=max(|Xi-Xj|，|Yi-Yj|，|Zi-Zj|)。
然后让你求它的最小生成树。
【算法分析】
标题是虽然是事实，但是明显是吓人的。。。。（为啥我也变成标题党了= =）
然后这题我的做法非常暴力。
我的方法如下（由于难以言表，请尽量结合程序围观。。。）：
首先必然的一件事是：用的kruskal  （MS拼错了，谁来纠正一下。。。）
先把点分开三个，分到不同的数组里，分别按x，y，z排序。
然后每个点设置一个已走步长：Lena[i] Lenb[i] Lenc[i]。
再建3个堆。
分别装的key值是类似这种a[i+Lena[i]].x-a[i].x。
然后每次取a,b,c三个堆中key值最小的出来，然后kruskal。
然后再把Lena[i]+1，再次把a[i+Lena[i]].x-a[i].x放入堆中。
（因为这个数肯定是增大了，所以能保证先把小的边弄了。）
最后并差集弄一下，就是一个完整的超暴力kruskal。
【其他】
Test # Score Time Memory Result 1 10 0.00s 9760 kB Correct! 2 10 0.00s 9760 kB Correct! 3 10 0.00s 9760 kB Correct! 4 10 0.00s 9760 kB Correct! 5 10 0.00s 9760 kB Correct! 6 10 0.04s 9920 kB Correct! 7 10 0.31s 9760 kB Correct! 8 10 0.30s 9760 kB Correct! 9 10 0.47s 9760 kB Correct! 10 10 0.80s 9760 kB Correct!
期待众神牛讲出正解。毕竟做人不能那么暴力。
【CODE】
#include #include #include const int N=100005;

struct Heap_Type{
int tot;
struct Node{int pos,key;}d[N],tmp;

void swap(Node &x,Node &y){tmp=x; x=y; y=tmp;}

void up(int k){
while (k>1){
if (d[k].key swap(d[k],d[k/2]);
k/=2;
}else break;
}
}

void down(int k){
int p;
while (k*2<=tot){
p=k*2;
if (p+1<=tot && d[p+1].key if (d[p].key swap(d[p],d[k]);
k=p;
}else break;
}
}

void ins(int key,int pos){
tot++;
d[tot].key=key;
d[tot].pos=pos;
up(tot);
}

void del(){
swap(d[1],d[tot]);
tot–;
down(1);
}
}Heapa,Heapb,Heapc;
struct Point{int x,y,z,pos;}a[N],b[N],c[N];
int n,times;
int F[N],Num[N],Lena[N],Lenb[N],Lenc[N];
long long ans;

int cmpa(const void *x,const void *y){return ((Point*)x)->x-((Point*)y)->x;}
int cmpb(const void *x,const void *y){return ((Point*)x)->y-((Point*)y)->y;}
int cmpc(const void *x,const void *y){return ((Point*)x)->z-((Point*)y)->z;}

void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[i].pos=i;
c[i]=b[i]=a[i];
Lena[i]=Lenb[i]=Lenc[i]=1;
F[i]=i; Num[i]=1;
}
qsort(a+1,n,sizeof(Point),cmpa);
qsort(b+1,n,sizeof(Point),cmpb);
qsort(c+1,n,sizeof(Point),cmpc);
Heapa.tot=Heapb.tot=Heapc.tot=0;
for (int i=1;i Heapa.ins(a[i+1].x-a[i].x,i);
Heapb.ins(b[i+1].y-b[i].y,i);
Heapc.ins(c[i+1].z-c[i].z,i);
}
}

int GF(int p){
int res=p,tmp;
while (F[res]!=res) res=F[res];
while (p!=res){
tmp=F[p];
F[p]=res;
p=tmp;
}
return res;
}

inline bool set_union(int x,int y){
if (GF(x)==GF(y)) return false;
times++;
if (Num[F[x]] Num[F[y]]+=Num[F[x]];
F[F[x]]=F[y];
}else{
Num[F[x]]+=Num[F[y]];
F[F[y]]=F[x];
}
return true;
}

void solve(){
times=1; ans=0;
int i;
while (times if (Heapa.d[1].key<=Heapb.d[1].key && Heapa.d[1].key<=Heapc.d[1].key){
i=Heapa.d[1].pos;
if (set_union(a[i].pos,a[i+Lena[i]].pos)) ans+=Heapa.d[1].key;
Lena[i]++;
Heapa.del();
if (i+Lena[i]<=n) Heapa.ins(a[i+Lena[i]].x-a[i].x,i);
}else
if (Heapb.d[1].key<=Heapa.d[1].key && Heapb.d[1].key<=Heapc.d[1].key){
i=Heapb.d[1].pos;
if (set_union(b[i].pos,b[i+Lenb[i]].pos)) ans+=Heapb.d[1].key;
Lenb[i]++;
Heapb.del();
if (i+Lenb[i]<=n) Heapb.ins(b[i+Lenb[i]].y-b[i].y,i);
}
else{
i=Heapc.d[1].pos;
if (set_union(c[i].pos,c[i+Lenc[i]].pos)) ans+=Heapc.d[1].key;
Lenc[i]++;
Heapc.del();
if (i+Lenc[i]<=n) Heapc.ins(c[i+Lenc[i]].z-c[i].z,i);
}
}
printf("%lldn",ans);
}

int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
init();
solve();
}