专题训练 1102（图论与数据结构）（未完成）

题目均为人工翻译英文，不清楚的地方 请 连蒙带猜 结合样例理解

ABC来自atcoder, DEF来自codeforces

震哥写的题解

校内链接，时限开了三年，各位同学可以继续做的鸭

T1 A

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e5+5;
const int INF = 1e8;//这里不可以设成1e9啊啊啊
int n, cnt=0;
ll a[N];
int dis[205][205], e[205][205];int main() {
    scanf("%d", &n);for(int i = 1; i <= n; i++) {
    ll x;scanf("%lld", &x);if(x) a[++cnt] = x;//如果为0，无边}if(cnt >= 130) {
     puts("3"); return 0;}//边界值for(int i = 1; i <= cnt; i++)for(int j = 1; j <= cnt; j++) if((a[i]&a[j]) && (i!=j)) e[i][j] = dis[i][j] = 1;else e[i][j] = dis[i][j] = INF;//赋初值int ans = INF;for(int k = 1; k <= cnt; k++) {
    for(int i = 1; i < k; i++)for(int j = i+1; j < k; j++)ans = min(ans, dis[i][j] + e[i][k] + e[k][j]);for(int i = 1; i <= cnt; i++)for(int j = 1; j <= cnt; j++)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);}//Floyed求最小环长度ans>cnt ? puts("-1") : printf("%d\n", ans);return 0;
}

T2 B

T3 C

T4 D

这题很清真啊~
只要注意一下时间上的优化，用$deep[i]$记录第$i$号点下面深度为$deep[i]$的所有点都已经染色

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e5+10;
struct qyx{
    int num, d, ans;} p[N];
int vis[N], deep[N];
int len=0, cnt=0, sum, n, m, Q;vector<int> e[N];//不知道为什么领接表会RE……就用Vector辽void Insert(int a, int b, int c) {
    p[++cnt].num = a;p[cnt].d = b;p[cnt].ans = c;
}void dfs(int k, int d, int ans, int fa) {
    if(deep[k]>d) return;deep[k] = d;//这是一个时间上优化，记录搜索的深度if(!vis[k]) vis[k] = ans, sum--;//如果颜色没有被改过for(int i = 0; i<e[k].size(); i++) {
    int y = e[k][i];if(y == fa) continue;if(d) dfs(y, d-1, ans, k);}
}int main() {
    scanf("%d%d", &n, &m);for(int i = 1, v, u; i <= m; i++) {
    scanf("%d%d", &u, &v);e[v].push_back(u);e[u].push_back(v);}scanf("%d", &Q);for(int i = 1,u, v, w; i <= Q; i++) {
    scanf("%d%d%d", &u, &v, &w);Insert(u, v, w);}sum = n;//倒着寻找颜色，因为颜色是会覆盖的for(int i = Q; i >= 1&&sum; i--) dfs(p[i].num, p[i].d, p[i].ans, 0);	for(int i = 1; i <= n; i++)printf("%d\n", vis[i]);return 0;
}

T5 E

T6 F

这题也清真~
但是我交了十几遍……是我太愚蠢……INF不能开到1e9，因为在Floyed中会爆

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e5+5;
const int INF = 1e8;//这里不可以设成1e9啊啊啊 
int n, cnt=0;
ll a[N];
int dis[205][205], e[205][205];int main() {
    scanf("%d", &n);for(int i = 1; i <= n; i++) {
    ll x;scanf("%lld", &x);if(x) a[++cnt] = x;}if(cnt >= 130) {
     puts("3"); return 0;}//因为与的性质，一旦不为0的数超过130，必然有三个数在同一位上皆为1（鸽巢原理）,那么必然存在最小环3//边界for(int i = 1; i <= cnt; i++)for(int j = 1; j <= cnt; j++) if((a[i]&a[j]) && (i!=j)) e[i][j] = dis[i][j] = 1;else e[i][j] = dis[i][j] = INF;int ans = INF;for(int k = 1; k <= cnt; k++) {
    for(int i = 1; i < k; i++)for(int j = i+1; j < k; j++)ans = min(ans, dis[i][j] + e[i][k] + e[k][j]);for(int i = 1; i <= cnt; i++)for(int j = 1; j <= cnt; j++)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);}//Floyed求最小环ans>cnt ? puts("-1") : printf("%d\n", ans);return 0;
}

T7 G

这道题目超级巧妙的说，其实只要能想到怎么建图，一切就很清真辽！
建图之前，在最外面框一圈0,，为什么呢，下面说。
我们把一种颜色看成一个点，只要与它相邻就建边，我们只考虑上下左右四个方向（因为题目中排除了对角线的情况），但只遍历右下两个方向，避免连边太多，因为左上的情况，它左上的点的连线会连向它。这很显然的叭！
这样就建成了一颗假的树（会出现环的呢），仔细观察一下，发现如果一个点 $x$ 是割点，这意味着什么呢，如果 $x$ 的子树和 $x$ 断开了联系，就与最外层的 $0$ 隔绝，也就意味着 $x$ 的子树所代表的所有颜色都被 $x$ 包裹在里面，太好了，答案已经出来了。
首先进行建图。
然后 $dfs$ 计算子树大小，这时候最外圈的 $0$ 就有用啦！ $0$在最外面，自然就是那个年纪最大的祖先！
然后遍历求割点，这里有一个坑！我刚开始就判断了一个点 $x$ 是否是割点，如果是就输出 $size[x]?1$，否则输出 $0$，但是这是不正确的，只能过 $9$ 个点（这可能是因为我 $RP$ 比较高，竟然能过 $9$ 个点）。因为这棵树是个假的树，它存在环，很有可能你求出的割点 $x$，分割出来的子树加上 $x$ 就是一个环或者子树直接与 $0$ 有连边，这个时候，这棵子树是不可以被加进答案里的，所以我们要判的其实是割边，如果是割边，就加入这个割边所相连的子树。
好了，做完了！

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1000100;
struct psx{
    int y, next;} e[N<<3];
int lin[N], size[N], vis[N], dfn[N], low[N], cnt[N];
int len=0, num, sum, root, n, m;
int a[1010][1010];
void add(int yy, int xx) {
    e[++len].next = lin[xx];lin[xx] = len;e[len].y = yy;
}void dfs(int k) {
    if(k > num) num = k;size[k] = vis[k] = 1;for(int i = lin[k]; i; i = e[i].next) {
    int y = e[i].y;if(vis[y]) continue;dfs(y);size[k] += size[y];}
}void tarjan(int x) {
    dfn[x] = low[x] = ++sum;for(int i = lin[x]; i; i = e[i].next) {
    int y = e[i].y;if(!dfn[y]) {
    tarjan(y);low[x] = min(low[x], low[y]);if(low[y] >= dfn[x]) cnt[x] += size[y];	}else low[x] = min(low[x], dfn[y]);}
}int main() {
    scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)scanf("%d", &a[i][j]);for(int i = 0; i <= n; i++)for(int j = 0; j <= m; j++) {
    if(a[i][j] != a[i+1][j]) add(a[i][j], a[i+1][j]),add(a[i+1][j], a[i][j]);if(a[i][j] != a[i][j+1]) add(a[i][j], a[i][j+1]),add(a[i][j+1], a[i][j]);} //建图dfs(0);//求子树tarjan(0);//求割点for(int i = 1; i < num; i++)printf("%d ", cnt[i]);printf("%d\n", cnt[num]);return 0;
}