图论做题记录
前言：大概是记录本人打比赛或者做题碰到的图论的部分题。
所有题目均已省以下宏：
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ull;
template <typename T> void inline read(T& x)
{
x=0; int f=1; char ch;
while((ch=getchar())>'9' || ch<'0') if(ch=='-') f=-1;
while(ch>='0' && ch<='9') x=x*10+(ch^'0'),ch=getchar();
x*=f;
}
T1
ABC277E
题意：
给定一个 \(n\) 个节点，\(m\) 条边的图，边权为 \(1\)，每条边有一个值 \(v(v\in\{0,1\})\)，为 \(1\) 则可用，否则不可用，有 \(k\) 个开关节点，表示可以将所有边的值异或 \(1\)，求节点 \(1\) 到节点 \(n\) 的最短路。
\(2 \leq n \leq 2\times10^5,1\leq m\leq 2\times 10^5,0 \leq k\leq n\)
分析：
考虑很难直接维护边权状态，考虑分层图。
具体的，对于初始值为 \(1\) 的边 (\(u,v\))，直接建边，初始值为 \(0\) 的边 (\(u,v\))，在 \(u+n,v+n\) 之间建边。开关节点 \(s\)，建 \(s\) 到 \(s+n\) 边权为 \(0\) 的边，然后跑一遍最短路就行了。
答案在 \(dis_n,dis_{2n}\) 中取 \(min\)。
for(int i = 1;i <= m;i++)
{
int u,v,kkk; read(u); read(v); read(kkk);
if(kkk) adde(u,v,1),adde(v,u,1);
else adde(u+n,v+n,1),adde(v+n,u+n,1);
}
for(int i = 1;i <= t;i++)
{
int x; read(x);
adde(x,x+n,0); adde(x+n,x,0);
}
T2
CF1715D
题意：
给定 \(q\) 对形如 \(i\ j\ x\) 的条件，你需要求出一个长度为 \(n\) 的数组 \(a\)，满足 \(q\) 个条件 \(a_i|a_j=x\) 都成立，且 \(a\) 的字典序最小（这里的 \(|\) 指的是或运算）。
\(1\leq n\leq 10^5,0\leq q\leq 2\times 10^5,0\leq x<2^{30}\)
分析：
直接维护 \(|\) 的结果不现实，考虑拆位分析。
对于一个限制 \(i\ j\ x\)，当 \(x\) 第 \(k\) 二进制位为 \(1\)，那么 \(a_i,a_j\) 中，至少有一个为 \(1\)，这时有一个贪心策略，尽量把 \(1\) 给 \(i,j\) 中下标更大的。
然后这样做可能会导致最后得到的序列不满足条件。
可以考虑建图，把 \(i,j\) 连一条 \(w\) 的边，用 \(g_{i,j}\) 表示 \(a_i\) 的第 \(j\) 位能否一定不填 \(1\)。
然后枚举所有二进制位 \(j\)，对于每个 \(i\)，遍历顶点为 \(i\) 的边。
- 边权 \(w\) 的第 \(j\) 位为 \(0\)，则当前这一位一定不能为 \(1\)。
- 设 \(v\) 为另一个顶点。
- 若 \(v<i\)，则另一个顶点一定已经被搜过了，如果 \(a_v\) 的第 \(j\) 为 \(0\)，那么 \(a_i\) 的第 \(i\) 位一定要设为 \(1\) 才能满足条件。
- 否则，\(v>i\)，如果 \(g_{v,j}\) 为 \(1\)，说明 \(v\) 不能填 \(1\)，但为了满足条件，\(a_i\) 的第 \(j\) 位必须为 \(1\)。
然后特判一下 \(i=j\) 的情况就行了。
int n,q,a[N],g[N][31];
bool dfs(int u,int j)
{
for(int i = head[u];~i;i=e[i].nxt)
{
int v = e[i].to;
if(!(e[i].w>>j&1)) continue;
if(u < v && g[v][j]) return 1;
else if(u >= v && !(a[v]>>j&1)) return 1;
}
return 0;
}
int main()
{
read(n); read(q); memset(head,-1,sizeof(head));
for(int i = 1;i <= q;i++)
{
int x,y,z; read(x); read(y); read(z);
for(int j = 0;j <= 30;j++) g[x][j] |= !(z>>j&1),g[y][j] |= !(z>>j&1);
if(x == y) a[x] = z;
else adde(x,y,z),adde(y,x,z);
}
for(int j = 0;j <= 30;j++)
for(int i = 1;i <= n;i++)
if(dfs(i,j))
a[i] |= (1<<j);
for(int i = 1;i <= n;i++) printf("%d%c",a[i]," \n"[i == n]);
return (0-0); // QwQ
}
T3
CF1715E
题意：
有 \(n\) 座城市，城市间有 \(m\) 条道路，通过第 \(i\) 条要花费 \(w_i\) 时间，任意两个城市间都有航班，坐航班从 \(u\) 到 \(v\) 要花费 \((u-v)^2\) 时间。
现在你最多可以坐 \(k\) 次航班，请求出从 \(1\) 号城市出发，到达其他所有城市的最短时间。
\(2\leq n\leq 10^5,1\leq m\leq 10^5,1\leq k\leq 20\)
分析：
这题最短路是少不了的，难处理的是航班。但是可以列出方程：\(dis_i=\min\limits_{j=1}^{n}dis_j+(i-j)^2\)。
我们可以拆一下式子：\(dis_i=dis_j+i^2+j^2-2\cdot i\cdot j\)
移项：\(dis_j+j^2=dis_i-i^2+2\cdot i\cdot j\)
然后发现这个东西跟斜率优化长得很像，可以设 \(y=dis_j+j^2,k=j,b=dis_i-i^2\)
然后就可以跑 \(k\) 遍斜率优化，每次都跑最短路，然后求出答案。
需要注意的几个点：
- 本题斜率优化与普通不同，没有 \(j \leq i\) 的限制，因此需要把所有的 \(j\) 加入队列中，再转移。
- 在第 \(i\) 遍斜率优化时，需要用第 \(i-1\) 次得到的 \(dis\) 数组去转移。
const int N = 1e5+5;
struct graph
{
int to,nxt,w;
graph(int tt,int nn,int ww)
{
to=tt;nxt=nn;w=ww;
}
graph(){
}
}e[N<<1];
int head[N],idx;
void adde(int u,int v,int w) {e[idx]=graph(v,head[u],w);head[u]=idx++;}
struct pos
{
int x; LL v;
friend bool operator < (pos a,pos b)
{
return a.v > b.v;
}
};
priority_queue <pos> q;
int n,m,k;
bool vis[N];
LL dis[N],qq[N<<1],f[N];
LL Y(int i) {return f[i]+1LL*i*i;}
LL K(int i) {return 2LL*i;}
LL B(int i) {return f[i]-1LL*i*i;}
LL get(int i,int j) {return 1LL*(i-j)*(i-j);}
double slope(int i,int j)
{
if(i == j) return 1e8;
return 1.0*(Y(i)-Y(j))/(i-j);
}
void dij()
{
for(int i = 1;i <= n;i++) vis[i] = 0;
while(!q.empty())
{
pos tmp = q.top(); q.pop();
if(vis[tmp.x]) continue;
vis[tmp.x] = 1;
for(int i = head[tmp.x];~i;i = e[i].nxt)
{
int j = e[i].to;
if(dis[j] > dis[tmp.x]+e[i].w)
{
dis[j] = dis[tmp.x]+e[i].w;
q.push(pos{j,dis[j]});
}
}
}
while(!q.empty()) q.pop();
}
int main()
{
read(n); read(m); read(k);
memset(head,-1,sizeof(head));
for(int i = 1;i <= m;i++)
{
int u,v,w; read(u); read(v); read(w);
adde(u,v,w); adde(v,u,w);
}
memset(dis,0x3f,sizeof(dis));
dis[1] = 0; q.push(pos{1,0LL});
dij();
while(k--)
{
int hh = 1,tt = 0;
qq[++tt] = 0;
for(int i = 1;i <= n;i++) f[i] = dis[i];
for(int i = 1;i <= n;i++)
{
while(hh < tt && slope(qq[tt-1],qq[tt]) >= slope(qq[tt-1],i)) --tt;
qq[++tt] = i;
}
for(int i = 1;i <= n;i++)
{
while(hh < tt && slope(qq[hh],qq[hh+1]) <= K(i)) ++hh;
int vv = qq[hh];
if(dis[i] > f[vv]+get(i,vv))
{
dis[i] = f[vv]+get(i,vv);
q.push(pos{i,dis[i]});
}
}
dij();
}
for(int i = 1;i <= n;i++) printf("%lld%c",dis[i]," \n"[i == n]);
return (0-0); // QwQ
}
T4
CF1844E
题意：
有一个 \(n \times m\) 的网格图，每个格子中可填入（\(A,B,C\)），满足对于任意 \(2 \times 2\) 大小的网格图，\(A,B,C\) 三个字母都要存在，两个相邻格子中字母不相同，现在有 \(k\) 个限制，要求 \((x1,y1)\) 和 \((x2,y2)\) 格子中的字母相同，请判断是否存在一种填字母方式，使得上述条件均满足。
分析：
由题目天然约束条件，可以得到在任意 \(2 \times 2\) 大小的网格图中，一定有一个对角线的字母相同，另一个对角线不相同，字母不太好表示，这里用 \(0,1,2\) 分别代替 \(A,B,C\)。
在 \(2 \times 2\) 大小的网格图中，只有两条对角线，可以分类讨论。
首先，我们定义一个网格中的数变成相邻网格中的数所要改变的数值为贡献。
1.大概类似这样
| 1 | 2 |
|---|---|
| 0 | 1 |
容易发现横着 \(1 \rightarrow 2\)，\(+1\) 贡献，竖着\(1 \rightarrow 0\)，\(+2\) 贡献（在模 \(3\) 意义下）。行列贡献不同。
2.大概类似这样
| 2 | 1 |
|---|---|
| 1 | 0 |
容易发现横竖都是 \(2 \rightarrow 1\),\(+2\) 贡献。行列贡献相同。
而行列贡献只能为 \(+1,+2\)，只有两种，因此可以把行，列看做节点（具体的就是，把 \(((i,j),(i+1,j))\) 这条边看做点，根据贡献的多少分为两个集合，跑二分图判定即可。
方法不止一种，还可以用带权并查集或者并查集扩展域，当然 \(2-sat\) 也是可行的。
我写的是带权并查集。
int n,m,k,fa[N],d[N];
int find(int x) // 这里还得继承
{
if(x == fa[x]) return x;
int rt = find(fa[x]);
d[x] += d[fa[x]];
return fa[x] = rt;
}
bool merge(int v,int x,int y)
{
int r1 = find(x),r2 = find(y);
if(r1 != r2)
{
d[r1] = d[y]+v-d[x];
fa[r1] = r2;
return 1;
}
return ((d[y]+v-d[x])%2 == 0); // 二分图
}
void solve()
{
read(n); read(m); read(k);
for(int i = 1;i <= n+m;i++) fa[i] = i,d[i] = 0;
int f = 1;
for(int i = 1;i <= k;i++)
{
int a1,b1,a2,b2; // /不等 \相等
read(a1); read(b1); read(a2); read(b2);
if(b1 < b2) f &= merge(1,a1,b1+n-1);
else f &= merge(0,a1,b2+n-1);
}
puts(f?"Yes":"No");
}
T5
Luogu P6833
题意：
给你一个 \(n \times m\) 的网格图，\((i,j)\) 的点权为 \(s_{i,j}\)，已知起点 \((n,a)\) 和两个终点\((1,b),(1,c)\)，求起点到两个终点的最短路，每个网格网格点权最多只算一次。
\(1 \leq n,m \leq 10^3,0 \leq s_{i,j} \leq 10^9,1 \leq a,b,c \leq m\)
分析：
此题有个错误解法：先求出起点到所有点的最短路，记录前驱，再便利求点权。
因为起点到两点总距离确定，但重复的路径一定是最短路，而我们要让路径总和最短，应该是最大化这个重复的路段（减的更多），所以做法错误。
可以枚举分叉点，然后对起点和两个终点分别跑一次最短路，得到三个 \(dij\) 数组，这样答案就是 \(min\{dis1_{i,j}+dis2_{i,j}+dis3_{i,j}-2*s_{i,j}\}\)
这样做复杂度是 \(O(nm+nm \log (nm))\)。
由于是网格图，此题可以不用建图。
int main()
{
memset(head,-1,sizeof(head));
read(n); read(m); read(a); read(b); read(c);
for(int i = n;i;i--)
for(int j = 1;j <= m;j++)
read(s[i][j]);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
vv[exc(i,j)] = s[i][j];
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
for(int k = 0;k < 4;k++)
{
int x = i+nxt[k][0],y = j+nxt[k][1];
if(x < 1 || x > n || y < 1 || y > m) continue;
adde(exc(i,j),exc(x,y),s[x][y]);
}
dij(exc(n,a),dis1);
dij(exc(1,b),dis2);
dij(exc(1,c),dis3);
LL ret = 2e16;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
ret = min(ret,dis1[exc(i,j)]+dis2[exc(i,j)]+dis3[exc(i,j)]-2*s[i][j]);
printf("%lld\n",ret);
return (0-0); // QwQ
}
T6
Luogu P7515[省选联考 2021 A 卷] 矩阵游戏
题意：
有一个 \(n \times m\) 的矩阵 \(a\) 和 \((n-1) \times (m-1)\) 的矩阵 \(b\)，已知 \(b_{i,j} = a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}\)，已知 \(b\)，请求出 \(a\)（无解输出 \(No\)，有多解输出任意。
\(1 \leq n,m \leq 300,0 \leq a_{i,j} \leq 10^6,0 \leq b_{i,j} \leq 4 \times 10^6\)。有多测。
分析：
如果 \(b\) 的相邻两元素相减，得到的也是关于四个元素的差值，也不好做，可以考虑把 \(a\) 的第一行第一列全部看成 \(0\)，然后可以递推求出其他元素，这里有一个限制很讨厌，\(0 \leq a_{i,j} \leq 10^6\)，我们要想办法利用起来。
要使 \(a\) 中所有元素满足条件，无疑就是让我们给每行每列加减一些数，而要使每个 \(2 \times 2\) 矩阵的元素和不变，则相邻两个数要加的值应该为相反数，也就是说每一行每一列要加的数的绝对值相等。设每一行加的数为 \(d_i\)，每一列要加的数为 \(d_{i+n}\)，那 \((i,j)\) 的元素实际值为 $a_{i,j}+(-1)^{i-1} \cdot d_i+(-1)^{j-1} \cdot d_{j+n} $，要满足限制，可以移项 \(-a_{i,j} \leq (-1)^{i-1} \cdot d_i+(-1)^{j-1} \cdot d_{j+n} \leq 10^6-a_{i,j}\)。不等式前后两项已知，中间未知，不就可以吧 \(i,j+n\) 抽象成节点，这不是很像差分约束吗？
但是，当 \(i,j\) 都为偶数，中间就是 \(d_i+d_{j+n}\) 是加法，不满足差分约束条件，怎么办？考虑画出矩阵:
\(\begin{pmatrix}d_1+d_{1+3}&-d_1+d_{2+3}&d_1+d_{3+3}\\d_2-d_{1+3}&-d_2-d_{2+3}&d_2-d_{3+3}\\d_3+d_{1+3}&-d_3+ d_{2+3}&d_3+d_{3+3}\end{pmatrix}\)
倾定行为奇数的，就把 \(d_i\) 变为相反数，列为偶数的，把 \(d_{j+n}\) 变为相反数，然后就会得到如下矩阵:
\(\begin{pmatrix}d_{1+3}-d_1&d_1-d_{2+3}&d_{3+3}-d_1\\d_2-d_{1+3}&d_{2+3}-d_2&d_2-d_{3+3}\\d_{1+3}-d_3&d_3-d_{2+3}&d_{3+3}-d_3\end{pmatrix}\)
然后发现，矩阵每一项都是两项差的形式了，这样就可以跑差分约束了。
输出的时候再判一下哪些修改了就行了。
const int N = 305;
vector <PII> g[N<<1];
int n,m,b[N][N],vis[N<<1],cnt[N<<1];
LL dis[N<<1],a[N][N];
void adde(int u,int v,int c){g[u].push_back({v,c});}
bool spfa()
{
queue <int> q;
while(!q.empty()) q.pop();
for(int i = 1;i <= n+m;i++) dis[i] = 2e16,vis[i] = cnt[i] = 0;
dis[1] = 0,vis[1] = 1;
q.push(1);
while(!q.empty())
{
int u = q.front(); q.pop();
vis[u] = 0;
for(auto x:g[u])
{
int j = x.fi,c = x.se;
if(dis[j] > dis[u]+c)
{
dis[j] = dis[u]+c;
cnt[j] = cnt[u]+1;
if(cnt[j] >= n+m+1) return 1;
if(!vis[j])
{
vis[j] = 1;
q.push(j);
}
}
}
}
return 0;
}
void solve()
{
read(n); read(m);
for(int i = 1;i <= n+m;i++) g[i].clear();
for(int i = 2;i <= n;i++)
for(int j = 2;j <= m;j++)
read(b[i][j]);
for(int i = 1;i <= n;i++) a[i][1] = 0;
for(int i = 1;i <= m;i++) a[1][i] = 0;
for(int i = 2;i <= n;i++)
for(int j = 2;j <= m;j++)
a[i][j] = b[i][j]-a[i-1][j-1]-a[i-1][j]-a[i][j-1];
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
int l = -a[i][j],r = 1e6-a[i][j];
if((i+j)&1) adde(i,j+n,r),adde(j+n,i,-l);
else adde(j+n,i,r),adde(i,j+n,-l);
}
if(spfa()) puts("NO");
else
{
puts("YES");
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
if((i+j)&1) a[i][j] -= dis[i];
else a[i][j] += dis[i];
if((i+j)&1) a[i][j] += dis[j+n];
else a[i][j] -= dis[j+n];
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
printf("%lld%c",a[i][j]," \n"[j == m]);
}
}
T7
Luogu P2474 [SCOI2008] 天平
题意：
有 \(n\) 个砝码，每个砝码重量可能为 \(1,2,3\) 克，你不清楚每个砝码的重量，但你知道任意两个砝码的重量关系，给你一个 \(n \times n\) 的字符关系矩阵，第 \(i\) 行 \(j\) 列的字符 + 表示砝码 \(i\) 比砝码 \(j\) 重，- 表示砝码 \(i\) 比砝码 \(j\) 轻，= 表示砝码 \(i\) 和砝码 \(j\) 一样重，? 表示两者关系未知。
现在把两个砝码 \(A,B\) 放在天平左边，需要选出另外两个砝码 \(x,y\) 放在天平右侧，有多少种选法使得左边的天平重 \((c1)\)，一样重 \((c2)\)，右边重 \((c3)\)？(只有结果保证唯一确定的选法才统计在内)。
\(4 \leq n \leq 50\)。
分析：
我们考虑把重量相同的砝码缩点，把重量轻的点向重量重的点连边，那么建出来的图回事一个最长链为 \(3\) 的 \(DAG\)。
然后考虑枚举放在右边的砝码 \(x,y\) 是什么以及 \(A,B,x,y\) 的重量，只需要 \(check\) 答案即可。
通过枚举我们知道了一些砝码的重量，对于其他的砝码，容易知道，当一个点的入度为 \(0\) 时，意味着通过已知关系我们知道没有其他砝码比他轻，所以把他设为 \(1\) 即可，当一个点的出度为 \(0\)，同理，所以把他设为 \(3\)，而对于其他的砝码，我们把它设为 \(2\) 就好了，然后判断一下是否合法即可，如果有解的话这一定是一组合法解。
时间复杂度 \(O(81n^2)\)，空间复杂度 \(O(n^2)\)。
const int N = 55;
int n,fa[N],rd[N],cd[N],st[3],ans[3],cl[N];
char op[N][N];
vector <int> g[N];
int find(int x){return fa[x] = (x == fa[x]?x:find(fa[x]));}
bool merge(int x,int y)
{
int r1 = find(x),r2 = find(y);
if(r1 == r2) return 0;
fa[r1] = r2;
return 1;
}
int calc(int a,int b)
{
if(a == b) return 1;
if(a > b) return 0;
return 2;
}
bool check()
{
for(int i = 1;i <= n;i++)
if(cl[i])
{
if(!cl[find(i)]) cl[find(i)] = cl[i];
else if(cl[find(i)] != cl[i]) return 0;
}
for(int i = 1;i <= n;i++)
if(find(i) == i && !cl[i])
{
if(!rd[i]) cl[i] = 1;
else if(!cd[i]) cl[i] = 3;
else cl[i] = 2;
}
for(int i = 1;i <= n;i++) for(auto x:g[i]) if(cl[i] >= cl[x]) return 0;
return 1;
}
int main()
{
int x,y; read(n); read(x); read(y);
for(int i = 1;i <= n;i++) scanf("%s",op[i]+1);
for(int i = 1;i <= n;i++) fa[i] = i;
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) if(op[i][j] == '=') merge(i,j);
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) if(op[i][j] == '+') g[find(j)].push_back(find(i)),rd[find(i)]++,cd[find(j)]++;
for(int i = 1;i <= n;i++)
for(int j = i+1;j <= n;j++)
{
if(i == x || i == y || j == x || j == y) continue;
for(int k = 0;k < 3;k++) st[k] = 0;
for(int a = 1;a <= 3;a++)
for(int b = 1;b <= 3;b++)
for(int c = 1;c <= 3;c++)
for(int d = 1;d <= 3;d++)
{
for(int k = 1;k <= n;k++) cl[k] = 0;
cl[x] = a,cl[y] = b,cl[i] = c,cl[j] = d;
st[calc(a+b,c+d)] |= check();
}
if(st[0]+st[1]+st[2] == 1) for(int k = 0;k < 3;k++) ans[k] += st[k];
}
for(int i = 0;i < 3;i++) printf("%d%c",ans[i]," \n"[i == 2]);
return (0-0); // QwQ
}
T8
Luogu P1646 [国家集训队] happiness
题意：
有一个 \(n \times m\) 的矩阵，可以选择把每个点染成黑白其中一种颜色，每个点染成不同的颜色有不同的奖励，同时，当相邻两个点染得颜色相同时，也会有额外奖励，问如何染色会让奖励和最大。
\(1 \leq n,m \leq 100\)，所有奖励均是小于等于 \(5000\) 的非负整数。
三倍经验：P4313,P1361
分析：
非常经典的最小割题目，答案是奖励和减去最小割。
一个点只能选黑白一种颜色，那么就相当于二选一，我们建 \(S \rightarrow (i,j),(i,j) \rightarrow T\) 两条边，边权分别为选黑白点的贡献，跑一个最小割就是不选奖励小的，显然正确。
对于同选黑点的每个奖励，我们新建一个点 \(x\)，然后建 \(S \rightarrow x,x \rightarrow v1,x \rightarrow v2\)，三条边，边权分别为这个奖励 \(+\infty,+\infty\)，这样做是正确的，因为同样考虑最小割，不选奖励小的，如果选白点奖励小，那最小割的结果是白点，否则是选黑点，因此这也正确。
同选白点同理，连向 \(T\) 即可。
memset(head,-1,sizeof(head));
read(n); read(m);
S = 0,T = 5*n*m+1;
int ret = 0;
for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) read(x),adde(S,exc(i,j),x),ret += x;
for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) read(x),adde(exc(i,j),T,x),ret += x;
for(int i = 1;i < n;i++) for(int j = 1;j <= m;j++) read(x),adde(S,exc(i,j)+1*n*m,x),adde(exc(i,j)+1*n*m,exc(i,j),1e7),adde(exc(i,j)+1*n*m,exc(i+1,j),1e7),ret += x;
for(int i = 1;i < n;i++) for(int j = 1;j <= m;j++) read(x),adde(exc(i,j)+2*n*m,T,x),adde(exc(i,j),exc(i,j)+2*n*m,1e7),adde(exc(i+1,j),exc(i,j)+2*n*m,1e7),ret += x;
for(int i = 1;i <= n;i++) for(int j = 1;j < m;j++) read(x),adde(S,exc(i,j)+3*n*m,x),adde(exc(i,j)+3*n*m,exc(i,j),1e7),adde(exc(i,j)+3*n*m,exc(i,j+1),1e7),ret += x;
for(int i = 1;i <= n;i++) for(int j = 1;j < m;j++) read(x),adde(exc(i,j)+4*n*m,T,x),adde(exc(i,j),exc(i,j)+4*n*m,1e7),adde(exc(i,j+1),exc(i,j)+4*n*m,1e7),ret += x;
printf("%d\n",ret-dinic());
T9
Luogu P4001 [ICPC-Beijing 2006] 狼抓兔子
题意：
给定一个 \(n \times m\) 的网格，左上角的点为 \((1,1)\)，右下角的点为 \((n,m)\)，有三种类型的道路：\(1.(x,y) \rightleftarrows (x+1,y),2.(x,y) \rightleftarrows (x,y+1),3.(x,y) \rightleftarrows (x+1,y+1)\)。
一条边需要消耗代价才能被删除，求使这张图不连通的最小代价。
\(3 \leq n,m \leq 1000\)。
分析：
考虑把边串起来，然后跑最小割（因为我不知道咋分析），注意建n双向边。
memset(head,-1,sizeof(head));
read(n); read(m);
S = exc(1,1),T = exc(n,m);
for(int i = 1;i <= n;i++) for(int j = 1;j < m;j++) read(x),adde(exc(i,j),exc(i,j+1),x);
for(int i = 1;i < n;i++) for(int j = 1;j <= m;j++) read(x),adde(exc(i,j),exc(i+1,j),x);
for(int i = 1;i < n;i++) for(int j = 1;j < m;j++) read(x),adde(exc(i,j),exc(i+1,j+1),x);
printf("%lld\n",dinic());
当然也可以平面图转对偶图跑最短路，具体的，边把这个网格分割为若干平面，我们可以把这些平面看做点，连接平面的边看作边，跑最短路即可。 `
void build()
{
S = 0,T = (n-1)*(m-1)*2+1;
for(int i = 1;i < n;i++)
for(int j = 1;j < m;j++)
{
adde(exc(i,j,0),exc(i,j,1),c[i][j]);
if(i == 1) adde(exc(i,j,1),T,a[i][j]);
else adde(exc(i,j,1),exc(i-1,j,0),a[i][j]);
if(i == n-1) adde(S,exc(i,j,0),a[i+1][j]);
if(j == 1) adde(S,exc(i,j,0),b[i][j]);
if(j == m-1) adde(exc(i,j,1),T,b[i][j+1]);
else adde(exc(i,j,1),exc(i,j+1,0),b[i][j+1]);
}
}
int main()
{
memset(head,-1,sizeof(head));
read(n); read(m);
for(int i = 1;i <= n;i++) for(int j = 1;j < m;j++) read(a[i][j]);
for(int i = 1;i < n;i++) for(int j = 1;j <= m;j++) read(b[i][j]);
for(int i = 1;i < n;i++) for(int j = 1;j < m;j++) read(c[i][j]);
build();
dij();
printf("%lld\n",dis[T]);
return (0-0); // QwQ
}
T10
CF1900E
题意：
有一个 \(n\) 个点 \(m\) 条边的有向图 \(G\)，每个顶点 \(u\) 的权值为 \(a_u\)。
对他进行操作：若存在三元组 \((a,b,c)\)，使得 \(a\) 到 \(b\) 有一条边，\(b\) 到 \(c\) 有一条边，但是 \(a\) 到 \(c\) 没有边，则连一条 \(a\) 到 \(c\) 的边。重复执行上述操作直到这样的三元组不存在。
当上述操作完成后，请计算图中最长的 不经过相同的点 的路径长度，并计算这些最长路径中，路径上的点权值和 最小 是多少。
\(1 \leq n,m \leq 2 \times 10^5,0 \leq a_i \leq 10^9\)。
分析：
如果有一个三元组 \((a,b,c)\) 满足条件，那么最优的路径一定不会选择 \(a \rightarrow c\)，因为如果选择走这条边，路径长度为 \(1\)，而如果走 \(a \rightarrow b,b \rightarrow c\)，这条路径的长度为 \(2\)。
因此题目中的三元组加边后，走这些新加的边的答案一定不会比走原图的边优，因此这些操作完全可以不执行。
因此这题就是一个经典的，缩点，跑拓扑排序的题目了。
const int N = 2e5+5;
struct graph
{
int to,nxt;
graph(int tt,int nn)
{
to = tt;nxt = nn;
}
graph(){
}
}e[N];
int head[N],idx;
void adde(int u,int v){e[idx] = graph(v,head[u]),head[u] = idx++;}
int n,m,a[N],dfn[N],low[N],id[N],vis[N],tim,scc,rd[N],cd[N],f[N],siz[N];
LL dp[N],val[N];
stack <int> st;
map <PII,int> mp;
vector <int> g[N];
void tarjan(int u)
{
dfn[u] = low[u] = ++tim;
st.push(u);
vis[u] = 1;
for(int i = head[u];~i;i = e[i].nxt)
{
int j = e[i].to;
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u],low[j]);
}
else if(vis[j]) low[u] = min(low[u],dfn[j]);
}
if(dfn[u] == low[u])
{
int y;
scc++;
do
{
y = st.top(); st.pop();
vis[y] = 0;
id[y] = scc;
siz[scc]++;
val[scc] += a[y];
}while(y != u);
}
}
void init()
{
for(int i = 1;i <= n;i++) dfn[i] = low[i] = id[i] = vis[i] = 0;
for(int i = 1;i <= scc;i++) val[i] = f[i] = rd[i] = cd[i] = siz[i] = 0,dp[i] = 1e15,g[i].clear();
while(!st.empty()) st.pop();
scc = tim = 0;
mp.clear();
}
void solve()
{
read(n); read(m);
for(int i = 1;i <= n;i++) head[i] = -1;
for(int i = 0;i < idx;i++) e[i] = graph(0,0);
idx = 0;
for(int i = 1;i <= n;i++) read(a[i]);
for(int i = 1;i <= m;i++)
{
int u,v; read(u); read(v);
adde(u,v);
}
for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i);
for(int i = 1;i <= n;i++)
for(int j = head[i];~j;j = e[j].nxt)
{
int k = e[j].to;
if(id[i] == id[k]) continue;
if(!mp.count({id[i],id[k]}))
{
g[id[i]].push_back(id[k]);
mp[{id[i],id[k]}] = 1;
rd[id[k]]++;
cd[id[i]]++;
}
}
queue <int> q;
for(int i = 1;i <= scc;i++) if(!rd[i]) q.push(i),dp[i] = val[i],f[i] = siz[i];
while(!q.empty())
{
int u = q.front(); q.pop();
for(auto x:g[u])
{
if(f[x] < f[u]+siz[x])
{
f[x] = f[u]+siz[x];
dp[x] = dp[u]+val[x];
}
else if(f[x] == f[u]+siz[x]) dp[x] = min(dp[x],dp[u]+val[x]);
--rd[x];
if(!rd[x]) q.push(x);
}
}
int r1 = 0;
LL r2 = 1e15;
for(int i = 1;i <= scc;i++)
if(!cd[i])
{
if(f[i] > r1) r1 = f[i],r2 = dp[i];
else if(f[i] == r1) r2 = min(r2,dp[i]);
}
printf("%d %lld\n",r1,r2);
init();
}
T11
CF852D
题意：
有一个 \(n\) 个点，\(m\) 条边的带权无向图，有 \(n1\) 支团队，第 \(i\) 个团队在 \(x_i\) 点上，要把一些团队安排到其他点上，使得至少有 \(k\) 个点上至少有团队，移动所需时间为边权，安排这些点所需时间是移动所有点的所需时间的最大值，问至少需要多少时间满足要求，无法满足要求输出 -1。
\(1 \leq n \leq 600,1 \leq m \leq 2 \times 10^5,1 \leq k \leq n1 \leq min(n,200)\)。
分析：
将一个团队从 \(x_i\) 移动到 \(j\) 点的最小时间就是 \(x_i\) 到 \(j\) 的最短路，因此可以先 \(n^3\) 预处理出任意两点间的最短路。
然后如果存在一种方案，使得在时间 \(x\) 内能满足条件，那么更大的时间 \(y\) 也一定满足。
那么我们可以二分最大时间，对于 \(x_i\) 到 \(j\) 的距离小于等于 \(x\) 的就连一条边，然后跑一个最大匹配，看匹配数量是否大于等于 \(k\) 即可。
const int N = 605;
int n,m,n1,m1,a[N],dis[N][N],vis[N],match[N];
vector <int> g[N];
bool dfs(int u)
{
for(auto x:g[u])
if(!vis[x])
{
vis[x] = 1;
if(match[x] == 0 || dfs(match[x])){match[x] = u;return 1;}
}
return 0;
}
int check(int x,int cnt = 0)
{
for(int i = 1;i <= n;i++) g[i].clear(),match[i] = 0;
for(int i = 1;i <= n;i++) for(int j = 1;j <= n1;j++) if(dis[i][a[j]] <= x) g[i].push_back(j);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n1;j++) vis[j] = 0;
cnt += dfs(i);
}
return cnt;
}
int main()
{
read(n); read(m); read(n1); read(m1);
for(int i = 1;i <= n1;i++) read(a[i]);
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) dis[i][j] = 1e9;
for(int i = 1;i <= n;i++) dis[i][i] = 0;
for(int i = 1;i <= m;i++)
{
int u,v,w; read(u); read(v); read(w);
dis[u][v] = dis[v][u] = min(dis[u][v],w);
}
for(int k = 1;k <= n;k++) for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) if(i != j && i != k && j != k) dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
int l = 0,r = 1e7;
while(l < r)
{
int mid = (l+r)/2;
if(check(mid) >= m1) r = mid;
else l = mid+1;
}
if(check(l) >= m1) printf("%d\n",l);
else puts("-1");
return (0-0); // QwQ
}
T12
CF1239D
题意：
有 \(n\) 个人，\(n\) 只猫，第 \(i\) 个人是第 \(i\) 只猫的主人，有 \(m\) 个关系 \(u,v\)，表示第 \(u\) 个人认识第 \(v\) 只猫。
要求选出 \(j\) 个人和 \(p\) 只猫，使得 \(j+p = n\)，且选出的任何人都不认识一只猫。
如果存在方案，请输出方案，否则报告无解。
\(1 \leq n \leq m \leq 10^6\)。
分析：
可以建一条 \(u \rightarrow v\) 的有向边，表示第 \(u\) 个人认识第 \(v\) 只猫，然后缩点，如果只有一个强连通分量则无解。
那么有这样的构造，找到一个没有出度的连通分量作为人，其他都是猫。
有余 \(tarjan\) 算法的本质，如果一个强连通分量有出边，由于它 \(dfs\) 的性质，一定会继续向下遍历，直到找到一个没有出度的强连通分量，因此第一个被找到的强连通分量一定没有出度。
const int N = 1e6+5;
struct graph
{
int to,nxt;
graph(int tt,int nn)
{
to = tt;nxt = nn;
}
graph(){
}
}e[N];
int head[N],idx;
void adde(int u,int v){e[idx] = graph(v,head[u]),head[u] = idx++;}
int n,m,dfn[N],low[N],scc,id[N],siz[N],vis[N],tot;
stack <int> st;
void tarjan(int u)
{
dfn[u] = low[u] = ++tot;
vis[u] = 1;
st.push(u);
for(int i = head[u];~i;i = e[i].nxt)
{
int j = e[i].to;
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u],low[j]);
}
else if(vis[j]) low[u] = min(low[u],dfn[j]);
}
if(dfn[u] == low[u])
{
int y;
++scc;
do
{
y = st.top(); st.pop();
vis[y] = 0;
id[y] = scc;
siz[scc]++;
}while(y != u);
}
}
void solve()
{
read(n); read(m);
for(int i = 1;i <= n;i++) head[i] = -1;
for(int i = 0;i <= idx;i++) e[i] = graph(0,0);
for(int i = 1;i <= n;i++) dfn[i] = low[i] = id[i] = vis[i] = 0;
for(int i = 1;i <= scc;i++) siz[i] = 0;
while(!st.empty()) st.pop();
tot = idx = scc = 0;
for(int i = 1;i <= m;i++)
{
int u,v; read(u); read(v);
if(u == v) continue;
adde(u,v);
}
for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i);
if(scc == 1) puts("No");
else
{
printf("Yes\n%d %d\n",siz[1],n-siz[1]);
int c = 0;
for(int i = 1;i <= n;i++) if(id[i] == 1) printf("%d%c",i," \n"[++c == siz[1]]);
for(int i = 1;i <= n;i++) if(id[i] != 1) printf("%d%c",i," \n"[++c == n]);
}
}
T13
CF888G
题意：
给定一个 \(n\) 的结点的无向完全图，每个点有一个权值 \(a_i\)，连接 \(i\) 和 \(j\) 的边的边权为 \(a_i \oplus a_j\)，求这个图的最小生成树。
\(1 \leq 2 \times 10^5 \leq n,0 \leq a_i \leq 2^{30}\)。
分析：
看到完全图，考虑 \(Boruvka\)，现在要维护一个块内的点跟其他块内的点的边的最小值，查询异或最小值，联想到 \(01-Trie\)，初始把所有 \(a_i\) 插入 \(Trie\) 树中，然后跑若干轮，枚举所有的块，对于每个块，找到能够使得他边权最小的另一块，并把他们合并，这样一次会合并两个块，一轮下来，剩余块数一定会减半，那么最多会有 \(O(\log n)\) 轮，这样做的复杂度是 \(O(n \log n \log a)\)。
合并两个连通块可以使用类似线段树合并的方式合并。
const int N = 2e5+5;
class trie01
{
public:
int ch[N*2*30][2],tot,siz[N*2*30],id[N*2*30];
void insert(int &rt,int dep,int i,int x)
{
if(!rt) rt = ++tot;
if(dep < 0)
{
id[rt] = i;
siz[rt] = 1;
return ;
}
int c = x>>dep&1;
insert(ch[rt][c],dep-1,i,x);
siz[rt]++;
}
PII query(int x,int pre,int w)
{
int ret = 0;
for(int i = 30;i >= 0;i--)
{
int c = w>>i&1;
if(ch[x][c] && siz[ch[x][c]]-siz[ch[pre][c]]) x = ch[x][c],pre = ch[pre][c];
else ret |= (1<<i),x = ch[x][c^1],pre = ch[pre][c^1];
}
return {ret,id[x]};
}
void merge(int &x,int y)
{
if(!x || !y) x |= y;
else
{
merge(ch[x][0],ch[y][0]);
merge(ch[x][1],ch[y][1]);
siz[x] = siz[ch[x][0]]+siz[ch[x][1]];
id[x] = id[y];
}
}
}ss;
int n,a[N],rt[N],fa[N],mn[N],ne[N];
int find(int x){return fa[x] = (x == fa[x]?x:find(fa[x]));}
int main()
{
read(n);
for(int i = 1;i <= n;i++) read(a[i]),fa[i] = i;
sort(a+1,a+1+n);
n = unique(a+1,a+1+n)-a-1;
for(int i = 1;i <= n;i++) ss.insert(rt[0],30,i,a[i]),ss.insert(rt[i],30,i,a[i]);
LL ret = 0;
while(1)
{
memset(mn,0x3f,sizeof(mn));
memset(ne,0,sizeof(ne));
int f = 0;
for(int i = 1;i <= n;i++)
{
int x = find(i);
auto now = ss.query(rt[0],rt[x],a[i]);
int y = find(now.se);
if(x != y)
{
if(now.fi < mn[x]) mn[x] = now.fi,ne[x] = y;
if(now.fi < mn[y]) mn[y] = now.fi,ne[y] = x;
}
}
for(int i = 1;i <= n;i++)
if(ne[i] && find(i) != find(ne[i]))
{
ret += mn[i];
ss.merge(rt[find(i)],rt[find(ne[i])]);
f = 1;
fa[find(ne[i])] = find(i);
}
if(!f) break;
}
printf("%lld\n",ret);
return (0-0); // QwQ
}
T14
CF1253F
题意：
给一张 \(n\) 个点 \(m\) 条边的带权无向连通图，结点 \(1 \sim k\) 为充电中心。
一个机器人在图中行走，假设机器人的电池容量为 \(c\)，则在任何时刻，机器人的电量 \(x\) 必须满足 \(0 \leq x \leq c\)。如果机器人沿着一条边权为 \(w\) 边从 \(i\) 走到 \(j\)，他的电量会减少 \(w\)。机器人可以在到达某个充电中心时把电量充满。
有 \(q\) 个询问，每次询问机器人要从 \(a\) 点到达 \(b\) 点，电池容量至少为多少，询问独立，保证 \(a,b\) 都是充电中心。
\(2 \leq k \leq n \leq 10^5,1 \leq m,q \leq 3 \times 10^5,1 \leq w_i \leq 10^9\)。
分析：
首先考虑最短路，所有充电中心都是起点，然后同时跑最短路，求出任意一个充电中心到某个点的最短距离，记到第 \(i\) 个点的最短路为 \(dis_i\)，那么经过一条边 \((i,j)\) 的最小代价是 \(dis_i+dis_j+w_{i,j}\)，那么一条边能走，就是这个最小代价小于等于 \(c\)，我们可以新到达一个充电中心，反复此过程即可。
然后求 \(a\) 到 \(b\) 是否可达，就是求 \(a\) 到 \(b\) 的一条路径上经过的边的代价的最大值是否小于等于 \(c\)。
这个问题很经典，可以根据这些最小代价建立 \(kruskal\) 重构树，然后最短简单路径上经过的边的最大值就是答案。
const int N = 1e5+5;
struct graph
{
int to,nxt,w;
graph(int tt,int nn,int ww)
{
to = tt;nxt = nn;w = ww;
}
graph(){
}
}e[N<<3];
int head[N],idx;
void adde(int u,int v,int w){e[idx] = graph(v,head[u],w),head[u] = idx++;}
struct pos
{
int x; LL v;
friend bool operator < (pos a,pos b)
{
return a.v > b.v;
}
};
struct edge
{
int u,v; LL w;
friend bool operator < (edge a,edge b)
{
return a.w < b.w;
}
}E[N];
int n,m,k,q,fa[N],dep[N],f[N][19];
LL dis[N],dp[N][19];
bool vis[N];
vector <pair<int,LL> > g[N];
int find(int x){return fa[x] = (x == fa[x]?x:find(fa[x]));}
bool merge(int x,int y)
{
int r1 = find(x),r2 = find(y);
if(r1 == r2) return 0;
fa[r1] = r2;
return 1;
}
void dij()
{
priority_queue <pos> q;
while(!q.empty()) q.pop();
for(int i = 1;i <= n;i++) dis[i] = 1e18;
for(int i = 1;i <= k;i++) dis[i] = 0,q.push({i,0});
while(!q.empty())
{
auto p = q.top(); q.pop();
int u = p.x;
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u];~i;i = e[i].nxt)
{
int j = e[i].to;
if(dis[j] > dis[u]+e[i].w)
{
dis[j] = dis[u]+e[i].w;
q.push({j,dis[j]});
}
}
}
}
void dfs(int u,int fa)
{
dep[u] = dep[fa]+1;
f[u][0] = fa;
for(auto x:g[u])
{
int j = x.fi;
if(j == fa) continue;
dfs(j,u);
dp[j][0] = x.se;
}
}
LL calc(int u,int v)
{
if(dep[v] > dep[u]) swap(u,v);
LL ret = 0;
for(int i = 18;i >= 0;i--) if(dep[f[u][i]] >= dep[v]) ret = max(ret,dp[u][i]),u = f[u][i];
if(u == v) return ret;
for(int i = 18;i >= 0;i--) if(f[u][i] != f[v][i]) ret = max(ret,max(dp[u][i],dp[v][i])),u = f[u][i],v = f[v][i];
ret = max(ret,max(dp[u][0],dp[v][0]));
return ret;
}
int main()
{
memset(head,-1,sizeof(head));
read(n); read(m); read(k); read(q);
for(int i = 1;i <= m;i++)
{
int u,v,w; read(u); read(v); read(w);
adde(u,v,w),adde(v,u,w);
}
dij();
for(int i = 0;i < idx;i += 2)
{
int v = e[i].to,u = e[i^1].to;
LL w = dis[v]+dis[u]+e[i].w;
E[i/2+1] = {u,v,w};
}
sort(E+1,E+1+m);
for(int i = 1;i <= n;i++) fa[i] = i;
int cnt = 0;
for(int i = 1;i <= m;i++)
{
int u = E[i].u,v = E[i].v;
if(merge(u,v))
{
g[u].push_back({v,E[i].w});
g[v].push_back({u,E[i].w});
cnt++;
if(cnt == n-1) break;
}
}
dfs(1,0);
for(int j = 1;j <= 18;j++)
for(int i = 1;i <= n;i++)
{
dp[i][j] = max(dp[i][j-1],dp[f[i][j-1]][j-1]);
f[i][j] = f[f[i][j-1]][j-1];
}
while(q--)
{
int u,v; read(u); read(v);
printf("%lld\n",calc(u,v));
}
return (0-0); // QwQ
}
T15
CF95C
题意：
给定一张 \(n\) 个点，\(m\) 条边的带权无向图，每个点有两个值 \(t,c\)，\(t\) 表示能走这个点最远沿边走 \(t\)，且不能在半路停下来，花费是 \(c\)。
给定起点和终点，求最小花费,无解输出 -1。
\(1 \leq n \leq 1000,0 \leq m \leq 1000,1 \leq w_i,t_i,c_i \leq 10^9\)。
分析：
可以先 \(O(n^2 \log m)\) 预处理两两点之间的最短路，然后 \(u\) 能够到达 \(v\)，当且仅当 \(dis_{u,v} \leq t_u\)，然后可以由 \(u\) 向 \(v\) 连一条边权为 \(c_u\) 的有向边，然后在新图上跑最短路即可。
int n,m,vis[N],st,ed;
LL dis[N];
vector <PII> g[N],e[N];
int main()
{
read(n); read(m); read(st); read(ed);
for(int i = 1;i <= m;i++)
{
int u,v,w; read(u); read(v); read(w);
g[u].push_back({v,w});
g[v].push_back({u,w});
}
for(int i = 1;i <= n;i++)
{
dij(i);
int t,c; read(t); read(c);
for(int j = 1;j <= n;j++) if(dis[j] <= t) e[i].push_back({j,c});
}
for(int i = 1;i <= n;i++) g[i] = e[i];
dij(st);
if(dis[ed] == 1e15) dis[ed] = -1;
printf("%lld\n",dis[ed]);
return (0-0); // QwQ
}
T16
CF95E
题意：
给定一个 \(n\) 个点，\(m\) 条边的无向图，你需要在图中加入若干条边，使得某个连通块的结点数量为 \(x\)，其中 \(x\) 的数码中只存在 \(4\) 或 \(7\)。
无解输出 -1。
\(1 \leq n,m \leq 10^5\)。
分析：
可以先用并查集合并求出若干连通块他们包含的结点数，那么题目就转化为最少由多少个连通块可以组合出题目所需要的 \(x\)。
这是个很显然的背包问题，\(dp_i\) 表示大小为 \(i\) 的块被组合出来需要的最少边数，这样做是 \(O(n^2)\) 的，显然无法通过。
但是发现 \(\sum\limits siz_i = n\)，那么这些连通块大小不相同的个数最多有 \(\sqrt n\) 个，然后我们可以将大小相同的连通块放在一起，这样就是一个完全背包了，然后就可以通过二进制分组或者单调队列优化了（\(c_i\) 表示 \(siz\) 为 \(i\) 的连通块个数）。
时间复杂度：\(O(n \log \sum\limits c_i)\) 或 \(O(n)\)。
const int N = 1e5+5;
int n,m,siz[N],fa[N],cnt[N],dp[N];
vector <PII> g;
int find(int x){return fa[x] = (x == fa[x]?x:find(fa[x]));}
bool merge(int x,int y)
{
int r1 = find(x),r2 = find(y);
if(r1 == r2) return 0;
fa[r1] = r2;
siz[r2] += siz[r1];
return 1;
}
bool check(int x)
{
while(x)
{
if(x%10 != 4 && x%10 != 7) return 0;
x /= 10;
}
return 1;
}
int main()
{
read(n); read(m);
for(int i = 1;i <= n;i++) fa[i] = i,siz[i] = 1;
for(int i = 1;i <= m;i++)
{
int u,v; read(u); read(v);
merge(u,v);
}
for(int i = 1;i <= n;i++) if(find(i) == i) cnt[siz[i]]++;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= cnt[i];j *= 2) g.push_back({j,i}),cnt[i] -= j;
if(cnt[i]) g.push_back({cnt[i],i});
}
memset(dp,0x3f,sizeof(dp));
dp[0] = 0;
for(auto x:g)
for(int i = n;i >= x.fi*x.se;i--)
dp[i] = min(dp[i],dp[i-x.fi*x.se]+x.fi);
int ret = 1e8;
for(int i = 1;i <= n;i++) if(check(i)) ret = min(ret,dp[i]-1);
if(ret == 1e8) ret = -1;
printf("%d\n",ret);
return (0-0); // QwQ
}
T17
JOI 2014 Final」飞天鼠
题意：
有 \(n\) 棵树，第 \(i\) 棵树高 \(h_i\)，一只小鼠初始位于 \(1\) 号树 \(x\) 高度。现在有 \(m\) 条航线，表示从 \(u_i\) 号树飞到 \(v_i\) 号树需要 \(t_i\) 秒（双向），飞行过程中，他离地面的高度会每秒下降 \(1\) 米，小鼠必须保证飞到 \(v_i\) 号树时不会高于树，也不会低于地面，他可以通过在 \(u_i\) 号树上以一米每秒的速度向上（向下）奔波，现在他需要到 \(n\) 号树的最高处，请求出最短时间，不能到达则输出 -1。
\(1 \leq n,m \leq 10^5,h_i,x,t_i \leq 10^9\)。
分析：
如果小鼠能通过某条边从 \(u\) 飞到 \(v\)，他会直接走。
如果小鼠能通过某条边从 \(u\) 飞到 \(v\) 树顶，他会现在 \(u\) 向下走奔波若干次，再到达 \(v\)。
如果存在两棵树 \(u,v\) 和连接它们的一条边 \((u,v,w)\)，并且满足 \(abs(h_u-h_v) \geq w\)，那么小鼠一定可以从高的那棵树飞向矮的那棵树，那么如果当前高度不足以飞行，他会向上奔走若干次，再飞行。
然后就按照上述说法跑最短路就行了。
const int N = 1e5+5,M = 3e5+5;
struct graph
{
int to,nxt,w;
graph(int tt,int nn,int ww)
{
to = tt;nxt = nn;w = ww;
}
graph(){
}
}e[M<<1];
int head[N],idx;
void adde(int u,int v,int w){e[idx] = graph(v,head[u],w),head[u] = idx++;}
struct pos
{
int x,h; LL v;
friend bool operator < (pos a,pos b)
{
return a.v > b.v;
}
};
int n,m,sx,a[N],vis[N];
priority_queue <pos> q;
int main()
{
memset(head,-1,sizeof(head));
read(n); read(m); read(sx);
for(int i = 1;i <= n;i++) read(a[i]);
for(int i = 1;i <= m;i++)
{
int u,v,w; read(u) ;read(v); read(w);
adde(u,v,w),adde(v,u,w);
}
LL ret = 2e18;
q.push({1,sx,0});
while(!q.empty())
{
auto p = q.top(); q.pop();
int u = p.x,h = p.h;
if(u == n) ret = min(ret,p.v+a[n]-h);
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u];~i;i = e[i].nxt)
{
int j = e[i].to,t = e[i].w;
if(h-t >= 0 && h-t <= a[j]) q.push({j,h-t,p.v+t});
else if(h-t < 0 && a[u] >= t) q.push({j,0,p.v+t-h+t});
else if(h-t > a[j]) q.push({j,a[j],p.v+h-t-a[j]+t});
}
}
if(ret == 2e18) ret = -1;
printf("%lld\n",ret);
return (0-0); // QwQ
}
T18
CF1887B
题意：
给定一张 \(n\) 个点的无向完全图和 \(t\) 组边集，边集 \(i\) 的大小为 \(m_i\)。每到达一个结点，你必须至少等待 \(1\) 秒才能继续前进。每条边的通过时间都是 \(0\) 秒。第 \(i\) 秒时，边集 \(a_i\) 中的边可以通行，其余边不能通行。第 \(0\) 秒时，你从结点 \(1\) 出发。判断是否可以在 \(k\) 秒到达结点 \(n\)。如果可以，求出从结点 \(1\) 到结点 \(n\) 的最小用时。
\(2 \leq n \leq 2 \times 10^5,1 \leq t \leq 2 \times 10^5,0 \leq m_i \leq min(\frac{n(n-1)}{2},2 \times 10^5)\)。
分析：
首先有一个做法，就是枚举已经走的时间，然后用数组记录能走到哪些点，但是这样是 \(O(nk)\) 的，显然会 \(T\)，换一种思路。
对每个边集存能走他的时间，然后在跑最短路的时候，\(upper_bound\) 找到对应边集的某个时间，更新答案（感觉太抽象了说不出来）。
const int N = 2e5+5;
struct pos
{
int x,v;
friend bool operator < (pos a,pos b)
{
return a.v > b.v;
}
};
int n,t,dis[N],vis[N];
vector <PII> g[N];
vector <int> ee[N];
void dij()
{
priority_queue <pos> q;
while(!q.empty()) q.pop();
for(int i = 1;i <= n;i++) dis[i] = 1e9;
dis[1] = 0;
q.push({1,0});
while(!q.empty())
{
auto p = q.top(); q.pop();
int u = p.x;
if(vis[u]) continue;
vis[u] = 1;
for(auto x:g[u])
{
int j = x.fi,v = x.se;
auto now = upper_bound(ee[v].begin(),ee[v].end(),dis[u]);
if(now == ee[v].end()) continue;
if(*now < dis[j])
{
dis[j] = *now;
q.push({j,dis[j]});
}
}
}
}
int main()
{
read(n); read(t);
for(int i = 1;i <= t;i++)
{
int x; read(x);
for(int j = 1;j <= x;j++)
{
int u,v; read(u); read(v);
g[u].push_back({v,i});
g[v].push_back({u,i});
}
}
int x; read(x);
for(int i = 1;i <= x;i++)
{
int v; read(v);
ee[v].push_back(i);
}
dij();
if(dis[n] == 1e9) dis[n] = -1;
printf("%d\n",dis[n]);
return (0-0); // QwQ
}
T19
ABC317G
题意：
给定一个 \(n\) 行 \(m\) 列的矩阵，其中 \(1 \sim n\) 各出现了 \(m\) 次，你可以进行任意次操作，每次操作可以把一行任意重排，最后要使得矩阵每一列都是一个长度为 \(n\) 的排列，如果有解，输出方案，否则报告无解。
\(1 \leq n,m \leq 100\)。
分析：
可以建一条 \(i \rightarrow a_{i,j}\) 的边，然后循环 \(m\) 次，每次找最大匹配，看是否为 \(n\)，然后删除匹配上的边，最后再输出答案即可。
时间复杂度：\(O(n^2m^2)\)。
const int N = 105;
int n,m,g[N][N],vis[N],match[N],ans[N][N],c[N];
bool dfs(int u)
{
for(int i = 1;i <=n;i++)
if(!vis[i] && g[u][i] > 0)
{
vis[i] = 1;
if(!match[i] || dfs(match[i])){match[i] = u;return 1;}
}
return 0;
}
int main()
{
read(n); read(m);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
int x; read(x);
g[i][x]++;
}
for(int i = 1;i <= m;i++)
{
int cnt = 0;
for(int j = 1;j <= n;j++) match[j] = 0;
for(int j = 1;j <= n;j++)
{
for(int k = 1;k <= n;k++) vis[k] = 0;
cnt += dfs(j);
}
if(cnt == n) for(int j = 1;j <= n;j++) g[match[j]][j]--,ans[match[j]][++c[j]] = j;
else {puts("No");return (0-0);}
}
puts("Yes");
for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) printf("%d%c",ans[i][j]," \n"[j == m]);
return (0-0); // QwQ
}
T20
CF1005F
题意：
给定一张 \(n\) 个顶点，\(m\) 条边的带权无向图，求这个图有多少最短路径树，如果有 \(x\) 个，若 \(x < k\) 输出 \(x\) 和所有的方案，否则，输出 \(k\) 和任意不同的 \(k\) 个方案。
\(2 \leq n \leq 2 \times 10^5,n-1 \leq m \leq 2 \times 10^5,1 \leq k \leq 2 \times 10^5,m \cdot k \leq 10^6\)。
分析：
先求出一棵最短路径树，然后暴力枚举每个节点可能得父亲，时间复杂度：\(O(n+mk)\)。
const int N = 2e5+5;
struct graph
{
int to,nxt,w;
graph(int tt,int nn,int ww)
{
to = tt;nxt = nn;w = ww;
}
graph(){
}
}e[N<<1];
int head[N],idx;
void adde(int u,int v,int w){e[idx] = graph(v,head[u],w),head[u] = idx++;}
struct pos
{
int x; LL v;
friend bool operator < (pos a,pos b)
{
return a.v > b.v;
}
};
priority_queue <pos> q;
int n,m,k,vis[N<<1],pre[N],sum,dis[N],ret = 1;
vector <int> g[N];
void dij()
{
q.push({1,0});
for(int i = 1;i <= n;i++) dis[i] = 1e9;
dis[1] = 0;
while(!q.empty())
{
auto p = q.top(); q.pop();
int u = p.x;
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u];~i;i = e[i].nxt)
{
int j = e[i].to;
if(dis[j] > dis[u]+e[i].w)
{
dis[j] = dis[u]+e[i].w;
g[j].clear();
g[j].push_back(i/2+1);
q.push({j,dis[j]});
}
else if(dis[j] == dis[u]+e[i].w) g[j].push_back(i/2+1);
}
}
}
void dfs(int u)
{
if(u == n+1)
{
for(int i = 1;i <= m;i++) printf("%d",vis[i]);
puts("");
--ret;
if(!ret) exit(0);
return ;
}
for(auto x:g[u]) vis[x] = 1,dfs(u+1),vis[x] = 0;
}
int main()
{
memset(head,-1,sizeof(head));
read(n); read(m); read(k);
for(int i = 1;i <= m;i++)
{
int u,v; read(u); read(v);
adde(u,v,1), adde(v,u,1);
}
dij();
memset(vis,0,sizeof(vis));
for(int i = 2;i <= n;i++)
if(1LL*ret*(int)g[i].size() > k) {ret = k;break;}
else ret *= (int)g[i].size();
printf("%d\n",ret);
dfs(2);
return (0-0); // QwQ
}