[COCI 2009/2010 – Constest #7 RESTORAN]AC、随机算法、非完美

【题外话】
这题之前写过一个题解了。
地址是：http://hi.baidu.com/edwardmj/blog/item/592566ad221c3ac07cd92a87.html
之前的算法没有AC。然后看了到处转了一转，又围观了神牛的代码。
各种构造法弄到头晕。。。
Orz。。。还是没看懂。然后我写起了当时扬言要写的随机算法。
【算法分析】
同样是当作树来DFS。
DFS时就判断当前点有没有1这种颜色。没有的话染1。
再判断有没有2这种颜色。没有的话染2。
否则得话，染颜色rand()%2+1。
然后出来以后还没染得，就看两边缺啥就染啥。
如果无解的话，重新染。直到无解10次那就真无解。
否则输出。
【评测结果】
Test # Score Time Memory Result 1 6.5 0.00s 6652 kB Correct! 2 6.5 0.00s 6652 kB Correct! 3 6.5 0.00s 6652 kB Correct! 4 6.5 0.00s 6652 kB Correct! 5 52.0 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.01s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 6 52.0 0.50s 9696 kB Correct! 0.09s 6652 kB Correct! 0.00s 6652 kB Correct! 0.13s 9696 kB Correct! 0.12s 7608 kB Correct! 0.19s 8288 kB Correct! 0.11s 7416 kB Correct! 0.12s 7944 kB Correct! 【CODE】
#include #include #include const int N=105555;
struct edge{int x,y,c,next,op;}g[N*2];
int n,e,times=0;
int ls[N],du[N],c1[N],c2[N];
bool v[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].c=0;
g[++e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].op=e-1; g[e].c=0;
}

void init(){
e=0;
memset(ls,0,sizeof(ls));
memset(du,0,sizeof(du));
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]++;
}
}

void draw(int t,int co){
g[t].c=co; g[g[t].op].c=co;
if (co==1){c1[g[t].x]++; c1[g[t].y]++;}
else{c2[g[t].x]++; c2[g[t].y]++;}
}

void dfs(int p){
for (int t=ls[p];t;t=g[t].next)
if (!v[g[t].y]){
v[g[t].y]=true;
if (!c1[p]) draw(t,1);
else if (!c2[p]) draw(t,2);
else draw(t,rand()%2+1);
dfs(g[t].y);
}
}

void work(){
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
memset(v,false,sizeof(v));
for (int i=1;i<=e;i++) g[i].c=0;
for (int i=1;i<=n;i++)
if (!v[i]){
v[i]=true;
dfs(i);
}
for (int t=1;t<=e;t++)
if (!g[t].c)
if (!c1[g[t].x] && du[g[t].x]>1 || !c1[g[t].y] && du[g[t].y]>1) draw(t,1);
else draw(t,2);
bool flag=true;
for (int i=1;i<=n;i++)
if (du[i]>1 && (!c1[i] || !c2[i])) flag=false;
if (!flag){
if (times<10){
times++;
work();
return;
}
printf("0n");
}
else
for (int i=1;i printf("%dn",g[i].c);
}

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