Graph Traing
Boboniu Walks on Graph
https://codeforces.com/problemset/problem/1394/B
题目大意: 给定一张图有$n$个点$m$条边，每条边的权值从$1$ ~ $m$并且每条边的权值互相不相同，这张图中一个点的最大的出度是$k$,然后求$k$元组，这个$k$元组的第$i$个位置代表着出度数为$i$的点走他的边权从小到大为第$c_i$的边，问多元组最多有多少种
解题思路: 首先我们可以发现这样子一件事情，因为$k$的范围并不大，因此如果我们暴力去枚举多元组的样子最多也只有$9!$种，那么我们是否可以有一种很快速的$check$方法来检查一种多元组是否合法呢？首先我们可以想这样一件事情，因为对于每一个点最后都能跳回到自己，所以最后的结果必定是一个环，那么对于一个环来说我们可以粗略的将其看成一个集合，然后我们给每个点刚开始随机一个数值。然后我们分析多元组的性质，对于任意一种多元组，第$i$位的跳跃到第$c_i$个，那么我们可以刚开始预处理这个东西，对于当前点的出度和当前去往点的序号记录一个数组然后加起来就可以了
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
typedef long long ll;
const int maxn = 1e6 + 10;
int n,m,k;
int sum[15][15];
int a[maxn],ansha,ans;
int res;
vector<pair<int,int>> edge[maxn];
void dfs(int now)
{
if(now == k + 1)
{
if(res == ansha) ans++;
return;
}
for(int i = 1;i <= now;++i)
{
res += sum[now][i];
dfs(now + 1);
res -= sum[now][i];
}
return;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
srand(time(NULL));
cin >> n >> m >> k;
for(int i = 1;i <= n;++i) a[i] = rand() * rand(),ansha += a[i];
for(int i = 1,u,v,w;i <= m;++i)
{
cin >> u >> v >> w;
edge[u].push_back({w,v});
}
for(int i = 1;i <= n;++i) sort(edge[i].begin(),edge[i].end());
for(int i = 1;i <= n;++i)
{
int sz = edge[i].size();
for(int j = 0;j < sz;++j)
{
auto to = edge[i][j].second;
sum[sz][j + 1] += a[to];
}
}
dfs(1);
cout << ans << "\n";
return 0;
}Slipper
(https://vjudge.net/contest/517945#problem/C)
题目大意: 给定一棵树，结点个数为$n (1 \leq n \leq 1e5)$,给定每条树边连接的两个结点和对应的边权，除此之外可以进行若干次魔法，若$|dep_u - dep_v| = k$，那么从$u$到$v$只需要$d$点边权，给定两个点$s$和$t$，求从$s$到$t$最少需要多少边权
解题思路: 我们可以刚开始这么思考，如果不考虑任何优化，我们可以将每个点放到对应的一个存储容器中，这个容易用$dep$ 来标记，如果两个容器相差$k$，那么我们对于两个集合中的点进行一一连边即可。但是这样子实际的时间复杂度很大，那么我们考虑优化建边。根据上面的思考，我们可以发现一个性质只有层与层之间才会连接一条边，其实很多边是重复的，那么我们对于每一个层来说我们可以建一个点，表示层，那么我们对于每一个点来说，连向这个层，那么对于层与层之间的，我们可以从$u$往$u + k$建一条边，同时也可以从$u + k$往$u$建边，但是只有一层层点是不够的，因为原来的树点连过来的边权是$0$，那么我们再建一层层点来跑最短路即可
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
const int maxn = 6e6 + 10;
const int maxm = 1e6 + 10;
const ll inf = 1e18;
int tot;
struct node
{
int u,v,w,nxt;
}edge[maxn << 1];
int head[maxn];
inline void add(int u,int v,int w)
{
edge[++tot].u = u,edge[tot].v = v,edge[tot].w = w,edge[tot].nxt = head[u],head[u] = tot;
}
int n,dep[maxm],k,p,s,t,mxdep;
void dfs(int s,int fa)
{
dep[s] = dep[fa] + 1;
mxdep = max(mxdep, dep[s]);
for(int i = head[s];i;i = edge[i].nxt)
{
int to = edge[i].v;
if(to == fa) continue;
dfs(to,s);
}
}
void dij()
{
vector<int> vis(3 * n + 10, 0);
vector<ll> dis(3 * n + 10, inf);
dis[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> que;
que.push({0, s});
while(!que.empty())
{
auto now = que.top().second;
que.pop();
if(vis[now])
continue;
vis[now] = 1;
for(int i = head[now];i;i = edge[i].nxt)
{
int to = edge[i].v;
ll ww = edge[i].w * 1ll;
if(dis[to] > dis[now] + ww)
{
dis[to] = dis[now] + ww;
que.push({dis[to], to});
}
}
}
printf("%lld\n",dis[t]);
}
void solve()
{
tot = 0;
scanf("%d",&n);
// cin >> n;
mxdep = 0;
for(int i = 1;i <= n + n + n + 10;++i) head[i] = 0;
for (int i = 1, u, v, w; i <= n - 1;++i)
{
scanf("%d %d %d",&u,&v,&w);
// cin >> u >> v >> w;
add(u,v,w);
add(v,u,w);
}
dfs(1, 0);
scanf("%d %d",&k,&p);
scanf("%d %d",&s,&t);
for (int i = 1; i <= n;++i)
{
add(i,dep[i] + n,0);
add(dep[i] + n + n,i,0);
}
for (int l = 1; l <= n;++l)
{
int r = l + k;
if(r > mxdep)
break;
add(l + n,r + n + n,p);
add(r + n + n,l + n,p);
}
dij();
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
scanf("%d", &T);
// cin >> T;
while(T--)
{
solve();
}
return 0;
}Ela and the Wiring Wizard
https://codeforces.com/contest/1737/problem/D
题目大意: 给定一张图，图有$n$个点$m$条边$(2 \leq n \leq 500,n - 1\leq m \leq 100000)$每次可以进行若干次操作，操作如下所示
选择两条边$(u,v)$和$(v,w)$删除$(u,v)$然后连接$(u,w)$，代价是$(u,v)$的边权
问从节点$1$到节点$n$最少需要多少次
解题思路: 刚开始拿到题目的时候发现没有任何思路，模拟样例可以发现一个性质，就是无论最后怎么样，最后只有一条从$1$到$n$的边使用
那么我们可以提出猜想，是否从$1$到$n$只需要连接一条路呢？
接下来的部分参考了$pzr$佬的
我们可以做出反证感性理解一下，假设我们有多条路到$n$，其中分别是$1 -> u_1 -> u_2 -> n$,设$u_1 ->u_2$的距离是$w_1$，另外一条从$1 -> u_1$权值是$w_2$
首先就放着这两条边，边权是$w_1 + w_2$
如果让我们把所有的边都变成$w_1$,那么就是$2w_1$
或者我们把所有边变成$w_2$，那么就是$2w_2$
那么进行修改后我们总能贪心取到最小的
分析样例之后，我们发现建边有成自环和非自环的情况
分析非自环的情况，那么对于一条边来说，就是去修改$dis(1,u) + dis(v,n)$的次数然后再加上$1$次走到的贡献
那么接下来考虑自环的情况，如果有自环的话最多可能存在几个自环呢？
我们可以把自环看成是一个点，设自环点是$x$,那么我们额外花费一个贡献连接$x$,从$1$到$x$再从$x$到$n$的距离相加然后乘贡献，这个$x$相当于中间的一个断点去更新整张图，因此实际上最多也就只有一个
那么对于这一种题目来说，分析完整道题目我们发现都是对边 这一个元素进行考虑
因为从一开始我们就在思考，从得出结论开始，再到实际上我去取哪条边最优
#define int long long
typedef long long ll;
const int maxn = 1e3 + 10;
const int inf = 1e9;
int dis[maxn][maxn],n,m;
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n >> m;
vector<array<int,3>> edge;
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j)
{
dis[i][j] = inf;
}
}
for(int i = 1;i <= n;++i) dis[i][i] = 0;
for(int i = 1,u,v,w;i <= m;++i)
{
cin >> u >> v >> w;
edge.push_back({u,v,w});
dis[u][v] = dis[v][u] = 1;
}
for(int k = 1;k <= n;++k)
{
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j)
{
chkmin(dis[i][j],dis[i][k] + dis[k][j]);
}
}
}
int ans = 1e18;
for(auto [u,v,w]:edge)
{
chkmin(ans,(dis[1][u] + 1 + dis[v][n]) * w);
chkmin(ans,(dis[1][v] + dis[u][n] + 1) * w);
for(int x = 1;x <= n;++x)
{
chkmin(ans,(min(dis[u][x],dis[v][x]) + dis[1][x] + dis[x][n] + 2) * w);
}
}
cout << ans << "\n";
}
}Session in BSU
题目大意: 给定$n(1 \leq n \leq 10 ^ 6)$场比赛，每场比赛有两个数字$a_i,b_i(1 \leq a_i ,b_i \leq 10 ^ 9)$ 代表可以在第几天考试，问最早可以在哪一天结束比赛，如果无法结束比赛输出$-1$
解题思路: 首先如果我们不看这个数据范围的话，那么是不是实际上可以一眼网络流，建立每个考试点和对应的天数点，跑最大流即可。但是观察一下数据范围实际上很大，那么我们就不能直接跑网络流，不过既然一眼网络流我们可以往建图这一个方向去思考这个问题。假设我对每场考试连一条边，那么是不是就代表着一件事情:我这一条边可以选择这两个点中的任意一个时间。那么整张图是不是就是一个森林了。然后我们来考虑一下每个连通块有什么性质，对于每个连通块中，我们都要让这个连通块的边数(考试场数) 小于等于点数(选择考试的天数)，那么对于每一个连通块中，我们假设边数是$num$,我们是不是选择第$num$大的天数就是这个连通块的答案
但是实际写起来之后发现这样子直接写会出现一些奇怪的问题，那么我们可以在思考刚刚形成的连通块是什么样子的，因为边数要小于等于点数，所以要么是一颗树，要么是一棵基环树，那么对于这两个来说我们只需要记录一个最大值和次大值即可，对于连通块是树的话输出次大值，基环树的输出最大值
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int maxn = 4e6 + 10;
int f[maxn],n,m,edgenum[maxn],sz[maxn],ansmx2[maxn],ansmx[maxn],val[maxn],cnt;
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
pair<int,int> edge[maxn];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> m;
for(int i = 1,u,v;i <= m;++i)
{
cin >> u >> v;
edge[i] = {u,v};
val[++cnt] = u,val[++cnt] = v;
}
sort(val + 1,val + 1 + cnt);
n = unique(val + 1,val + 1 + cnt) - (val + 1);
for(int i = 1;i <= n;++i) f[i] = i,sz[i] = 1,edgenum[i] = 0,ansmx[i] = i;
for(int i = 1;i <= m;++i)
{
auto [u,v] = edge[i];
u = lower_bound(val + 1,val + 1 + n,u) - val;
v = lower_bound(val + 1,val + 1 + n,v) - val;
int fu = getf(u);
int fv = getf(v);
if(fu == fv)
{
edgenum[fu]++;
}
else
{
f[fu] = fv;
sz[fv] += sz[fu];
edgenum[fv] += edgenum[fu] + 1;
vector<int> ha;
ha.push_back(ansmx2[fu]);ha.push_back(ansmx[fu]);
ha.push_back(ansmx2[fv]);ha.push_back(ansmx[fv]);
sort(ha.begin(),ha.end());
ansmx[fv] = ha[3];
ansmx2[fv] = ha[2];
}
}
int f = 1;
int res = 0;
for(int i = 1;i <= n;++i)
{
int fi = getf(i);
if(i == fi)
{
if(sz[i] < edgenum[i])
{
f = 0;
break;
}
if(edgenum[i] == sz[i]) chkmax(res,val[ansmx[i]]);
else chkmax(res,val[ansmx2[i]]);
}
}
if(!f)
{
cout << -1 << "\n";
return 0;
}
cout << res << "\n";
}Moment of Bloom
题目大意: 给定一个点数为$n$，边数为$m$的图$(1 \leq n,m \leq 3*10^5)$,初始所有点的点权为$0$。给定$q$次操作，每次操作给定两个点，你可以选择图上这两个点中任意一条简单路径，并且给这一条简单路径上面所有的点权加$1$，问经过$q$次操作这张图所有点的点权是否都是偶数，如果是的话输出$Y!ES$并且输出每次操作应该怎么操作，否则输出$N!O$并且输出最少还需要加几条边，特别注意的是$nq \leq 3 * 10^5$
解题思路: 首先遇到这样子的问题在一张图上面会很棘手，因为两个点之间可能有很多的路径，那么既然这样，我们先尝试简化一下这个问题。如果我们把这一个问题放在一棵树上面，那么两点之间的路径是不是就已经确定了。既然这样，什么时候会出现不行的情况呢？我们每次可以对路径的两个端点增加一个值，如果最后在这一棵树上面存在点的点权是奇数，那么是肯定输出$NO$的。然后由于点是成对出现的，那么点也会是成对落单的，我们记录奇数个数的点为$num$个，那么最后需要的边数就是$\frac{num}{2}$个
然后对于原题来说我们已经把题目化成在树上面了，那么我们直接在树上类似$LCA$找祖先结点沿路径输出即可
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int maxn = 3e5 + 10;
struct graph
{
vector<int> edge[maxn];
inline void add(int u,int v)
{
edge[u].push_back(v);
edge[v].push_back(u);
}
}g1,g2;
int n,m,deg[maxn];
pair<int,int> op[maxn];
int f[maxn],p[maxn],dep[maxn];
int getf(int x)
{
return x == f[x] ? x : f[x] = getf(f[x]);
}
void dfs(int s,int fa)
{
dep[s] = dep[fa] + 1;
p[s] = fa;
for(auto to:g2.edge[s])
{
if(to == fa) continue;
dfs(to,s);
}
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1,u,v;i <= m;++i)
{
cin >> u >> v;
g1.add(u,v);
}
int q;
cin >> q;
for(int i = 1;i <= q;++i) cin >> op[i].first >> op[i].second,deg[op[i].first]++,deg[op[i].second]++;
int ct = 0;
for(int i = 1;i <= n;++i)
{
ct += (deg[i] & 1);
}
if(ct)
{
cout << "NO\n";
cout << ct / 2 << "\n";
return 0;
}
cout << "YES\n";
for(int i = 1;i <= n;++i) f[i] = i;
for(int i = 1;i <= n;++i)
{
for(auto to:g1.edge[i])
{
int fx = getf(i);
int fy = getf(to);
if(fx == fy) continue;
f[fy] = fx;
g2.add(i,to);
}
}
// cout << "?? " << "\n";
dfs(1,0);
for(int i = 1;i <= q;++i)
{
auto [u,v] = op[i];
vector<int> now;
vector<int> now2;
// cout << "?? ? " << u << " " << v << "\n";
while(dep[u] != dep[v])
{
if(dep[u] > dep[v]) now.push_back(u),u = p[u];
else now2.push_back(v),v = p[v];
}
while(u != v)
{
now.push_back(u);
now2.push_back(v);
u = p[u];
v = p[v];
}
reverse(now2.begin(),now2.end());
now.push_back(u);
for(auto to:now2)
{
now.push_back(to);
}
cout << now.size() << "\n";
for(auto to:now)
{
cout << to << " ";
}
cout << "\n";
}
}
Factory Balls
**题目大意: ** 给定一个球，球被划分成为$n$个区域，然后有$k$种颜色的油漆桶，有$m$个装备，球的每个区域在初始状态都是$1$
接下来可以进行以下三种操作若干次，一种是将这个球放入油漆桶里面，这个球没有被装备安装的部分全部会感染上这个颜色，一种是在这个球上面安装一个装备，一种是给这个球脱下一种装备
问这个球的区域是否可以达到给定的目标状态，如果可以的话输出最小的步数，否则输出$-1$
特别的是$1 \leq n,m,k \leq 10$
解题思路: 首先考虑数据范围，因为我们的数据范围实际上其实很小，那么我们可以进行状压来表示 当前的状态 和 目标状态 是否一致，如果一致是$1$否则就是$0$ 。然后我们就这样子$BFS$，我们进行搜索的时候的状态可以以当前的颜色和目标的颜色的差别以及装备的数目和种类，然后我们思考，当前状态更新一步的操作要么是去不变颜色更新装备状态，不变状态更新装备颜色，然后搜索即可
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int maxn = 1111;
const int inf = 1e9 + 7;
int n,k,m;
int col[maxn],vis[maxn];
vector<int> equ[maxn];
int dis[maxn][maxn];
int main()
{
// ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> k >> m;
for(int i = 1;i <= n;++i) cin >> col[i];
int s = 0;
for(int i = 0,num;i < m;++i)
{
cin >> num;
for(int j = 1,x;j <= num;++j)
{
cin >> x;
equ[i].push_back(x);
}
}
for(int i = 1;i <= n;++i)
{
if(col[i] == 1)
{
s |= (1 << (i - 1));
}
}
queue<pair<int,int>> que;
memset(dis,0x3f,sizeof dis);
// cout << "?1" << dis[s][0] << "??\n";
dis[s][0] = 0;
que.push({s,0});
while(!que.empty())
{
auto [nowcol,nowequ] = que.front();
que.pop();
// cout << "-----------------------------\n";
// cout << "now -> " << nowcol << " " << nowequ << "\n";
for(int i = 0;i < m;++i)
{
auto toequ = nowequ ^ (1 << i);
if(dis[nowcol][toequ] > dis[nowcol][nowequ] + 1)
{
dis[nowcol][toequ] = dis[nowcol][nowequ] + 1;
que.push({nowcol,toequ});
}
}
for(int i = 1;i <= n;++i) vis[i] = 0;
for(int i = 0;i < m;++i)
{
if(nowequ >> i & 1)
{
for(auto to:equ[i])
{
vis[to] = 1;
}
}
}
for(int i = 1;i <= k;++i)
{
int tocol = nowcol;
for(int j = 1;j <= n;++j)
{
if(vis[j]) continue;
if(col[j] == i)
{
tocol |= (1 << (j - 1));
}
else
{
if(tocol >> (j - 1) & 1)
{
tocol ^= (1 << (j - 1));
}
}
}
// cout << i << " tocol ?? " << tocol << "\n";
if(dis[tocol][nowequ] > dis[nowcol][nowequ] + 1)
{
dis[tocol][nowequ] = dis[nowcol][nowequ] + 1;
que.push({tocol,nowequ});
}
}
}
// cout << (1 << (m)) - 1 << " " << dis[7][0] << " ??\n";
if(dis[(1 << (n)) - 1][0] >= inf) cout << -1 << "\n";
else cout << dis[(1 << (n)) - 1][0] << "\n";
return 0;
}
