题解 P7228 [COCI2015-2016#3] MOLEKULE

· · 题解

题解 P7228 [COCI2015-2016#3] MOLEKULE

我也来水题解了

思路分析

题目要求我们构造一种方案，确定一个n个点n-1条边的无向图各边方向，使产生的有向图中的最大连通块最小。很自然会想到树的情况，或者先考虑链的情况，不难得出只要原图上直接相连的点只要满足间隔地所连边都指向指出自己，或者说入度出度间歇地为0，就一定能得到为1的最小代价。例如：

1->2<-3->4<-5

和

    1<-8
    ^
 2<-3->4<-5
    v     v
    6     7

实现上，我们可以用一次无向图dfs解决问题。

从任意图中任一点p开始，先假定构造了一个有向图使刚好可以从该点遍历全图，dfs过程中将与该点p距离为奇数（或偶数）的边标记取反，再结合原边的情况取反即可。

其中最需要注意的是虽然是无向图，但由于最后输出的是是否与给出的边反向，建立无向图时依然需要考虑区分原边和反向边。这里我们选择将反向边存在MAXN以后的新区域（这样同时也可以用边的下标判断是不是原边），对于反向边遍历时需要调换方向的边即不需要调换，因此从哪个点开始dfs都没问题

代码

#include<iostream>
#define endl '\n'
using namespace std;
#define MAXN 100001
int n;
struct edge{
    int v;
    int next;
}e[MAXN<<1];
int head[MAXN];
bool towards[MAXN];//确认边要不要调换方向
bool f=0;//初始为0或1都没关系
bool vis[MAXN];
void dfs(int p)
{
    if(vis[p])
        return;
    vis[p]=1;
    f^=1;
    for(int i=head[p];i;i=e[i].next)
    {
        if(vis[e[i].v])
            continue;
        //f^=1;
        if(i>MAXN)
            towards[i-MAXN]=f^1;
        else
            towards[i]=f;
        dfs(e[i].v);
        //f^=1;
    }
    f^=1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,j=MAXN+1,u,v;i<n;i++,j++)
    {
        cin>>u>>v;
        e[i].v=v,e[i].next=head[u],head[u]=i;//加边
        e[j].v=u,e[j].next=head[v],head[v]=j;//无向图加反向边  
    }
    dfs(0);
    for(int i=1;i<n;i++)
        cout<<towards[i]<<endl;
    return 0;
}

其他

回到一开始，n个点n-1条边的图就一定是树吗？实际上，题面中并没有说这个n个点n-1条边的无向图是连通的（虽然测试点中是这样体现的），也许这个图可能是分别连通的两部分，甚至说不定可能有环和平行边（自环平行边大概一般都不考虑）。所以之前的思考其实是不全面的。

幸运的是，再次考虑我们刚才的思路。只需分别从每个点进行一遍dfs（不重置vis[]）即可；而对于存在环的部分dfs同样适用，只是不能保证奇数个节点的环上最小代价总为1；至于平行边的问题在dfs同时也可以不需要任何额外步骤就得到解决。

蒟蒻作题解，如有错误欢迎各位大佬指出

小错误是故意的w