[COCI 2009/2010 – Constest #7 RESTORAN]贪心骗分、未A、非完美算法

【题目地址】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();
}