Description
给你一个\(N *N\)的网格，初始\(M\)个格子\((a_i,b_i)\)被涂成黑色，其余为白色。每次可以将一些格子涂成黑色，规则如下如果存在三个格子\((x,y),(y,z),(z,x)\)满足\((x,y),(y,z)\)均为黑色，且\((z,x)\)为白色，那么我们可以把\((z,x)\)涂成黑色。输出不能继续操作时，黑格子的最大数量。
Hint
\(1<=N,M<=10^5,1<=a_i,b_i<=N\)，并且所有的\((a_i,b_i)\)互不相同。
Solution
先转化模型，将网格变成邻接矩阵，于是题目转化为：有一个有向图，如果x->y,y->z,加上z->x。重复该过程直到不能再添加。求最终图中有多少边。
首先，各个弱联通块之间互不影响，所以，每个弱联通块单独考虑。手玩一下发现
1、一条长度为2的链会构成一个三元环。
2、如果出现二元环，一定会出现自环
3、所有连向有自环的点的点，会出现自环
4、一旦出现二元环或者自环原弱联通块会变成完全图。
那么，我们考虑如何判断该联通块会不会出现二元环，或者自环。那么我们将弱联通块三染色，分类讨论：
1、染色失败，如果每种颜色都出现过，说明出现了二元环或者自环，原图最终一定是一个完全图；如果，只出现了一种或者两种颜色，说明无法增加新的边。
2、染色成功，则弱联通块的答案为，染色为0的点连向染色为1的点，染色为1的点连向染色为2的点，染色为2的点连向染色为0的点。
分类统计答案即可。
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
int n, m, ecnt, h[maxn], col[maxn];
ll cnt[5];
struct enode{
int v, n, w;
enode() {}
enode(int _v, int _n, int _w):v(_v), n(_n), w(_w) {}
}e[maxn << 1];
inline void addedge(int u, int v, int w) {
ecnt ++; e[ecnt] = enode(v,h[u],w); h[u] = ecnt;
}
int flag = 0;
void dfs(int u) {
cnt[col[u]] ++;
for(int i = h[u];~ i;i = e[i].n) {
if(e[i].w == 1) cnt[3] ++;
int v = e[i].v, tmp = (col[u] + e[i].w) % 3;
if(col[v] == -1) {
col[v] = tmp;
dfs(v);
}
else if(col[v] != tmp) flag = 1;
}
}
int main() {
scanf("%d%d", &n, &m); ecnt = 0;
memset(h,-1,sizeof(h));
for(int i = 1;i <= m;i ++) {
int u, v;
scanf("%d%d", &u, &v);
addedge(u,v,1);
addedge(v,u,2);
}
ll ans = 0;
memset(col,-1,sizeof(col));
for(int i = 1;i <= n;i ++) {
if(~ col[i]) continue;
cnt[0] = cnt[1] = cnt[2] = cnt[3] = 0;
col[i] = 0;
flag = 0;
dfs(i);
if(flag) {
ll tmp = cnt[0] + cnt[1] + cnt[2];
ans = ans + 1LL * tmp * tmp;
continue;
}
if(cnt[0] && cnt[1] && cnt[2]) {
ans = ans + cnt[0] * cnt[1] + cnt[1] * cnt[2] + cnt[2] * cnt[0];
continue;
}
ans = ans + cnt[3];
}
printf("%lld\n", ans);
return 0;
}
转载于:https://www.cnblogs.com/ezhjw/p/9520115.html
相关资源：JAVA上百实例源码以及开源项目
