[CF1444C]Team-Building

题目

传送门 to CF

思路

思路一定要开阔……我一开始 $\mathtt{y}\mathtt{y}$ 了个什么做法哟……

我一开始直接猜是 $\mathtt{d}\mathtt{f}\mathtt{s}$ 树这种线性的东西。然后开始努力的优化。首先思考到 “异色边” 只需要走过一次，因为一旦走过这个 “异色边” ，只要你认真地深搜，就会搜出这个环。但是 “同色边” 就不行了，所以考虑同色连通块缩点，缩成两个点即可（因为我们只在乎环的奇偶）。

然后一个点会被访问很多次。考虑把边排序后 $\mathtt{l}\mathtt{o}\mathtt{w}\mathtt{e}\mathtt{r}\_\mathtt{b}\mathtt{o}\mathtt{u}\mathtt{n}\mathtt{d}$ ，发现仍然不行，复杂度假了。于是考虑直接把所有同类的异色边拿出来。此时才发现是 并查集。

意识到带权并查集可以处理二分图之后，一切问题都解决了，只需要一个可回退的并查集就行。但是我在这里吃了个教训：回退不能改变树结构，必须是按秩合并。一旦路径压缩你就完蛋了。$\mathcal{O}(n\log n)$ 。

当然，如果你把连通块缩点了，你也可以路径压缩，把所有波及到的连通块暴力连接回去。可以优化到 $\mathcal{O}(\alpha n)$ ，但是我们并不需要这么优秀 😂

$2020/12/4\mathtt{u}\mathtt{p}\mathtt{d}\mathtt{a}\mathtt{t}\mathtt{e}$

突然意识到原本的做法完！全！可！行！（指同色连通块缩成两个点）

为啥一定要在原图上跑 $\mathtt{d}\mathtt{f}\mathtt{s}$ 树？我们姑且把边放在 $\mathtt{v}\mathtt{e}\mathtt{c}\mathtt{t}\mathtt{o}\mathtt{r}$ 里，每次用链式前向星加入有用的边然后造 $\mathtt{d}\mathtt{f}\mathtt{s}$ 树不就行了？这不就是线性的了？这不就是 $\mathcal{O}(n+m)$ 随便跑？

缩点也并不麻烦，每个连通块内随便找个点，然后到它距离为奇数和偶数的分到两边。

我感觉我真是蠢到爆炸……全地球可能很难找出一个像我一样蠢的蠢货了！

代码

#include 
#include 
#include 
#include 
using namespace std;
typedef long long int_;
inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}const int MaxN = 500005;struct UFS{vector< int > zxy; // fuckedint fa[MaxN], d[MaxN];int rnk[MaxN]; // 启发式合并inline int find(int a,int &x){if(a == fa[a]) return a;return find(fa[a],x ^= d[a]);}void init(int n){for(int i=1; i<=n; ++i){fa[i] = i, d[i] = 0;rnk[i] = 1;}zxy.clear();}/** @return 是否仍然为二分图 */inline bool merge(int a,int b){int da = 0, x = find(a,da);int db = 0, y = find(b,db);if(x == y) return da != db;if(rnk[x] > rnk[y]) swap(x,y);fa[x] = y, d[x] = da^db^1;rnk[y] += rnk[x]; // ensure Complexityzxy.push_back(x); return true;}void restore(){while(!zxy.empty()){int x = zxy.back();rnk[fa[x]] -= rnk[x];fa[x] = x, d[x] = 0;zxy.pop_back();}}
};
UFS xyx; // 并查集vector< pair<int,int> > cu; // 不铜的边
int col[MaxN]; // 每个点的颜色
bool cmp(const pair<int,int> &a,const pair<int,int> &b){if(col[a.first] != col[b.first])return col[a.first] < col[b.first];return col[a.second] < col[b.second];
}bool junk[MaxN]; // 不行的颜色
int main(){int n = readint(), m = readint();int k = readint();for(int i=1; i<=n; ++i)col[i] = readint();xyx.init(n); // 同色连通块直接连出来for(int i=1,a,b; i<=m; ++i){a = readint(), b = readint();if(col[a] == col[b])junk[col[a]] = junk[col[a]]or !xyx.merge(a,b);else{if(col[a] > col[b])swap(a,b); // 使其无序cu.push_back(make_pair(a,b));}}xyx.zxy.clear(); // 把 zxy 清空sort(cu.begin(),cu.end(),cmp);int_ ans = 0; // 最终答案for(int i=1,now=0; i<=k; ++i)if(!junk[i]) // 垃圾颜色跳过ans += now, ++ now;for(int l=0,r=0,len=cu.size(); l<len; l=r){bool ok = true; // 能否幸存if(junk[col[cu[l].first]] ||junk[col[cu[l].second]]){++ r; continue; // 内部已经不行了}while(r < len && // 保证不越界，小心 REcol[cu[r].first] == col[cu[l].first] &&col[cu[r].second] == col[cu[l].second]){if(!xyx.merge(cu[r].first,cu[r].second))ok = false; // 不行了++ r; // [l,r) 都是同类边}if(!ok) -- ans; // 又倒了一个xyx.restore(); // 重要：回归原样！}printf("%lld\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！