一般来说,我学习完每一个知识点都会写两篇博客,第一篇是基础知识和模板题,主要是为了整理思路加深理解;第二篇主要就是拿来记录做到的好题了。
大部分题解都用的欧拉回路的做法,但问题在于欧拉回路我用的不熟,所以它的方法我也没有怎么理解到;相较而言,二分图的做法我倒是很快就明白了,虽然中间证明建出来的图是二分图上面有点牵强,当如何证明不重要对吧,又不影响拿分……
这道题给我的启发就是,和矩阵游戏一样,如果需要两个节点之间存在某种联系的话,很有可能就可以通过建二分图来解决。你看,矩阵游戏是把行数和列数“连起来”,这道题是把“配对”的两个点连起来;矩阵游戏里面行和列是两类不相交的节点,而这道题“1点”和“-1点”也是两类不相交的节点。二分图的题目总有某些内在联系对吧。
代码不算多,相较于写的其它黑题,已经算是非常友好的了。
之前写了一篇这道题的题解,里面说得更详细:链接
#include<cstdio>
#include<cstring>
//#define zczc
using namespace std;
const int N=100010;
inline void read(int &wh){
wh=0;int f=1;char w=getchar();
while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
wh*=f;return;
}
int m;
bool odd[N],odd2[N];//在两棵树中某个节点的孩子数量是否为奇数
//graph中是二分图部分
namespace graph{
struct edge{
int t,next;
}e[N<<1];
int head[N],esum;
inline void add(int fr,int to){
esum++;
e[esum].t=to;
e[esum].next=head[fr];
head[fr]=esum;
return;
}
bool vis[N],black[N];
//二分图标记颜色
void dfs(int wh,bool color){
vis[wh]=true;
black[wh]=color;
for(int i=head[wh],th;i;i=e[i].next){
th=e[i].t;
if(vis[th])continue;
dfs(th,!color);
}
return;
}
}
//tree中是树的部分
//个人感觉分开来写要清晰一些
namespace tree{
struct edge{
int t,next;
}e[N];
int head[N],esum;
inline void add(int fr,int to){
esum++;
e[esum].t=to;
e[esum].next=head[fr];
head[fr]=esum;
return;
}
int decide[N];//标记每个节点为根的子树的“决定点”
bool second;
void dfs(int wh){
bool oddnum=false;//动态显示孩子数量的奇偶性
int son=0,last=0;//son是落单的孩子,last是方便“配对”孩子用的
for(int i=head[wh];i;i=e[i].next){
oddnum=!oddnum;
dfs(e[i].t);
son=e[i].t;
if(last==0)last=e[i].t;
else{
graph::add(decide[last],decide[e[i].t]);
graph::add(decide[e[i].t],decide[last]);
last=0;
}
}
if(second)odd2[wh]=oddnum;
else odd[wh]=oddnum;
//如果有奇数个孩子就取决于落单的孩子
if(oddnum)decide[wh]=decide[son];
//如果有偶数个孩子就自己决定
else decide[wh]=wh;
return;
}
void solve(){
//输入,没什么好说的
read(m);
int s1,root;
for(int i=1;i<=m;i++){
read(s1);
if(s1==-1)root=i;
else add(s1,i);
}
dfs(root);
memset(head,0,sizeof(head));
esum=0;
for(int i=1;i<=m;i++){
read(s1);
if(s1==-1)root=i;
else add(s1,i);
}
second=true;
dfs(root);
for(int i=1;i<=m;i++){
if(odd[i]!=odd2[i]){
printf("IMPOSSIBLE\n");
return;
}
}
printf("POSSIBLE\n");
for(int i=1;i<=m;i++){
if(graph::vis[i])continue;
graph::dfs(i,true);
}
for(int i=1;i<=m;i++){
if(odd[i])printf("0 ");
else{
if(graph::black[i])printf("1 ");
else printf("-1 ");
}
}
return;
}
}
signed main(){
#ifdef zczc
freopen("in.txt","r",stdin);
#endif
tree::solve();
return 0;
}