agc006_f
题目叙述
给一个有向图，对于三个点如果 \(u\rightarrow v\) ，\(v\rightarrow w\) （\(u,v,w\) 不一定两两不同），那么再连一条 \(w\rightarrow u\) 的边。求最终的总边数。图可能有自环。
题解
对每个弱连通块分别考虑。弱连通块定义为将有向边视为无向边的连通块。
将图用三种颜色红、黄、蓝染色。红色点只能向黄色点连边，黄色点只能向蓝色点连边，蓝色点只能向红色点连边。弱环定义为将所有边视为无向图形成的环。
如果不存在一个这样的染色方法，设块的大小为 \(x\)，那么将产生 \(x^2\) 条边。因为这样必然会有一个弱环满足他不能被染色。现在每次将这个弱环的边 \(u\rightarrow v\) ，\(v\rightarrow w\) 的边缩为 \(w\rightarrow u\) ，那么这个弱环必将不断缩小，并且依旧不能用三种颜色染色。最终将会缩小成一个自环。一个自环将把整个环传染成一个完全图。
如果一个图存在这样的染色方法，并且三种颜色都用上了，那么这个图必然还是只能红色点黄色点连边，黄色点只能向蓝色点连边，蓝色点只能向红色点连边。只要这个图存在一个三元环 \(u\rightarrow v,v\rightarrow w,w\rightarrow u\) ，那么对于任意 \(x\) 与 \(u\) 有边，那么必然会产生 \(x\rightarrow u,u\rightarrow w,w\rightarrow x\) 。所以这样下去对于任意红色点会与任意黄色点右边，任意黄色点会向任意蓝色点有边，任意蓝色点会向绿色点有边。这样会产生 \(r\cdot y+y\cdot b+b\cdot r\) 。其中 \(r,y,b\) 表示红色、黄色、蓝色点数量。
如果存在染色方法并且至多两种颜色用上了，可以发现不能连出任何新边。
这样做就行了。
实现
#include <cstdio>
using namespace std;
const int NN = 1e5 + 5, NM = 1e5 + 5;
int N, M;
struct E {
int v, nxt, fx;
E(int _v=0, int _nxt=0, int _fx=0) : v(_v), nxt(_nxt), fx(_fx) {}
};
struct Graph {
int head[NN], totE;
E edge[NM<<1];
void AddE(int u, int v, int fx) {
edge[++totE] = E(v, head[u], fx);
head[u] = totE;
}
} G;
int col[NN];
bool vis[NN];
int ys[] = {1, 2, 0};
int fanys[] = {2, 0, 1};
//0->1
//1->2
//2->0
int cnt[3], egnum = 0, cc;
bool Dfs(int u) {
vis[u] = 1;
cnt[col[u]] += 1;
int hoho = 0;
bool ret = 1;
for (int p = G.head[u]; p; p = G.edge[p].nxt) {
int v = G.edge[p].v;
++hoho;
if (vis[v]) {
if (G.edge[p].fx == 1 && col[v] != ys[col[u]]) {
ret = 0;
}
if (G.edge[p].fx == -1 && col[v] != fanys[col[u]]) {
//注意第一个 G.edge[p].fx == -1的条件
//以后限制能多写就多写
ret = 0;
}
continue ;
}
if (G.edge[p].fx == 1)
col[v] = ys[col[u]];
else col[v] = fanys[col[u]];
if (!Dfs(v)) //记得这句话
ret = 0;
}
egnum += hoho;
return ret;
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= M; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G.AddE(u, v, 1);
G.AddE(v, u, -1);
}
long long ans = 0;
for (int i = 1; i <= N; ++i) {
if (!vis[i]) {
cnt[0] = cnt[1] = cnt[2] = 0;
egnum = 0; //初始化！
bool jd = Dfs(i);
int sum = cnt[0] + cnt[1] + cnt[2];
//这里得 dfs完 cnt[0] cnt[1] cnt[2]才准确
if (!jd) ans += (long long)sum * sum;
else if (!cnt[0] || !cnt[1] || !cnt[2]) ans += egnum / 2;
else ans += (long long)cnt[0] * cnt[1] +
(long long)cnt[1] * cnt[2] +
(long long)cnt[2] * cnt[0];
}
}
printf("%lld\n", ans);
return 0;
}
/*
5 4
1 2
2 3
4 5
5 5
*/
总结
- 和三元环有关系的题考虑用三种颜色染色？