权威白癜风专家 http://news.39.net/bjzkhbzy/171218/5941620.html洛谷P封锁阳光大学
按照题意，每个顶点要不放河蟹，要不不放河蟹，而且相连的顶点不能具有相同的状态。因此我们可以将其抽象成二分图，即两种相连的顶点不能染成相同的颜色，对于每一个连通图，我们使用两种颜色通过DFS将其染色，只要有一个连通图不能染色成功，就直接得到结果“NO”,因为题中可能含有多个连通图，对第i个连通图，我用2i和2i+1表示两种颜色，这个连通图放的河蟹数就是用这两种颜色染成的顶点数最小的那种颜色的数量，即min(用2i染的顶点数量，用2i+1染的顶点数量)，最后每一个连通图求和就是最后的答案
#pragmaGCCoptimize(2)#includebits/stdc++.husingnamespacestd;#definepiacos(-1.0)#defineeexp(1.0)typedeflonglongll;constllmaxn=1e5+7;llN,M,col[];vectorllV[];boolflag;llKu;mapll,llMa;voidDFS(llu,llk)//将顶点u染成k{col=k;lli;for(i=0;iV.size();i++){llv=V;if(col[v]==0)//如果没有染过，将相连的顶点染色DFS(v,(k1)?k-1:k+1);elseif(col[v]==k)//如果染过了，并切发生了矛盾{flag=0;//标记return;}else;}return;}intmain(){//freopen(".../.txt","w",stdout);ios::sync_with_stdio(false);memset(col,0,sizeof(col));cinNM;lli,j;for(i=0;iM;i++){llu,v;cinuv;V.push_back(v);V[v].push_back(u);}flag=1;Ku=0;for(i=1;i=N;i++){if(col==0)//可能有多个连通图{if(!flag)//有一个不能成功染色的话直接就能得到结果了，可以减少时间break;Ku++;DFS(i,2*Ku);}}if(!flag)//有一个连通图不能成功染色{cout"Impossible"endl;return0;}llcnt=0,jie=0;for(i=1;i=N;i++)Ma[col]++;//将用每一种颜色染色的顶点数求出来for(i=1;i=Ku;i++){if(!Ma[2*i])//有的连通图可能只用了一种颜色，需要将另一种颜色补充进去，便于去最小值Ma[2*i]=0;if(!Ma[2*i+1])Ma[2*i+1]=0;jie+=min(Ma[2*i],Ma[2*i+1]);}coutjieendl;return0;}
更多有趣的内容
请长按
?
长按
