题解 CF19E 【Fairy】

hicc0305

2018-08-17 19:30:40

Solution

听说可以用LCT做。。。可是蒟蒻不会LCT。。。 首先,一个图一定是由一堆环和一堆链组成的。根据这道题,我们可以发现一个很好的性质,那就是,每一条链必然是一个二分图,每一个偶环,也必然是一个二分图,所以。。只剩下奇环。。不是二分图了。。 因此,我们要找的边是,被所有奇环覆盖的并且没有被偶环覆盖的边,因为,删掉这条边,原来的偶环变成了奇数条边,奇环变成了偶数条边,这两个环练了起来,又~~tm~~合成了一个奇环orz 也就是说我们要记录一条边被奇环和偶环覆盖的次数。覆盖的次数?怎么这么像运输计划。。因此我们想到了用树上差分来解决这个问题。 另外,这道题非常坑人,注意以下几点: 1.如果没有奇环,删那条边都可以,所以输出m条边 2.如果只有一个奇环,那么返祖边也要被算进答案。因为我们是用差分来求覆盖次数的,所以我们是从叶子节点往上,求子树和的,因此我们并不能遍历到返祖边,并没有把他算进答案。在有多个奇环的时候,返祖边是不可能能被算进答案的,因为返祖边只能覆盖自己的奇环(你可以在树上画画看),所以在有多个奇环的情况下,我们根本不用去管他。而在只有一个奇环的时候,他也要算进去了,做一个特判即可。当然,你把所有边领出来一起差分,把返祖边也差分到,是不用考虑这种情况的,这种情况只是针对在dfs的时候一起做差分的程序,这种程序是差分不到返祖边的(就像我)。 3.然后。。这道题其实还要考虑重边、自环。。。但是介于数据太水,你不去管也能过。。。 那么。。代码 ```cpp #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int fa[2000010],tago[2000010],tage[2000010],dep[2000010];//tag是差分数组,dep记录深度,回到深度小的就是返祖边了 int fr[2000010],eve[2000010],odd[2000010],f[2000010],fz;//eve记录偶环差分和,odd记录奇环差分和,fz是对于只有一个奇环时,存返祖边的编号 int n,m,num;//num记录的是奇环个数 vector < pair<int,int> > to[2000010]; vector <int> ans; void dfs(int u) { for(int i=0;i<to[u].size();i++) { int v=to[u][i].first; if(v==fa[u]) continue; if(!dep[v]) { dep[v]=dep[u]+1; fa[v]=u,fr[v]=to[u][i].second; dfs(v); eve[u]+=eve[v],odd[u]+=odd[v]; } else if(dep[v]<=dep[u])//不要写成<,因为有自环情况要考虑(尽管这些数据是不会WA的) { if((dep[v]-dep[u])&1) tage[u]++,tage[v]--;//偶环情况 else num++,tago[u]++,tago[v]--,fz=to[u][i].second;//奇环情况 } } eve[u]+=tage[u]; odd[u]+=tago[u]; } int solve() { int cnt=0; if(!numoddn)//没有奇环 { for(int i=1;i<=m;i++) ans.push_back(i); return m; } for(int i=1;i<=n;i++) if(odd[i]==num && !eve[i]) { cnt++; ans.push_back(fr[i]); } if(num==1)//一个奇环 { cnt++; ans.push_back(fz);//加上返祖边 } return cnt; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); int flag=1,it; for(int j=0;j<to[x].size();j++) if(to[x][j].first==y) flag=0,it=j; if(flag) { if(x==y) to[x].push_back(make_pair(y,i));//处理自环 else to[x].push_back(make_pair(y,i)),to[y].push_back(make_pair(x,i)); } else f[to[x][it].second]=1;//有重边就做标记 } for(int i=1;i<=n;i++) if(!dep[i]) { dep[i]=1; dfs(i); } int num=solve(); for(int i=0;i<ans.size();i++) if(f[ans[i]]) ans.erase(ans.begin()+i),num--,i--;//如果选中的边中有重边,删掉 printf("%d\n",num); sort(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); return 0; } ```