题解

BZOJ3706 反色刷

BZOJ3706 反色刷 题解

题目大意

P10777 BZOJ3706 反色刷

Solution

先考虑无解情况噻~

显然就是只关注黑边构成的图，如果一张连通黑图内有奇数度的点，肯定是不能构成欧拉回路的。证明根据欧拉回路的性质，可以翻我之前的博客。

接下来思考要最少多少次回路可以跑完黑边。

我们只考虑连通图，不连通情况就当做多张连通图来处理。

如果现在有一条起点终点都是 $u$ 的回路和起点终点都是 $v$ 的回路（当然回路上的边都是黑的），这两条回路可不可以只用一次回路就完成呢？

端详一下，因为现在只考虑连通图，所以 $u$，$v$ 一定是连通的。那么我们为什么没选到这条 $u\leftrightarrow v$ 之间的路径呢？想必是这条路径上是白边。那意味着我们可以往返走，即走两次，这样的话这条路径就反色了个寂寞，也就是它还是白色。

所以按照上面这种方法，两条回路势必可以连成一条回路，那么整个连通图最后肯定只有一条回路。

所以一个连通块最少做一次回路操作。

具体的答案就是有黑边的连通块个数。

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define ft first
#define sd second

const int N=1e6+5,INF=1e18;

int n,m,q,cnt;
int deg[N];
vector<pii> G[N]; 
bool vis[N],flg;
int top[N],cnttop[N];
struct edge{int u,v,w;}E[N];

void dfs(int u,int tp)
{
    vis[u]=1,top[u]=tp;
    for(pii v:G[u]){
        if(!vis[v.ft]){
            cnttop[tp]+=(v.sd==1);
            dfs(v.ft,tp);
        }
    }
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        G[u].push_back({v,w});
        G[v].push_back({u,w});
        if(w==1)
            deg[u]++,deg[v]++;
        E[i]={u,v,w};
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            flg=0;
            dfs(i,i);
            if(cnttop[i]>0)
                ++cnt;
        }
    scanf("%lld",&q);
    flg=0;
    for(int i=1;i<=q;i++){
        int op,x;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld",&x);
            x++;
            if(E[x].w){
                deg[E[x].u]--,deg[E[x].v]--;
                E[x].w^=1;
                if((deg[E[x].u]&1)||(deg[E[x].v]&1))
                    flg=1;
                else
                    flg=0;
                --cnttop[top[E[x].u]];
                if(cnttop[top[E[x].u]]==0)
                    cnt--;
            }else{
                deg[E[x].u]++,deg[E[x].v]++;
                E[x].w^=1;
                if((deg[E[x].u]&1)||(deg[E[x].v]&1))
                    flg=1;
                else
                    flg=0;
                ++cnttop[top[E[x].u]];
                if(cnttop[top[E[x].u]]==1)
                    cnt++;
            }
        }else{
            if(flg){
                puts("-1");
                continue;
            }
            printf("%lld\n",cnt);
        }
    }
    return 0;
}