2024.10.16校测
T1
题目描述
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵恰好有 \(need\) 条白色边的权值和最小的生成树。题目保证有解。
输入格式
第一行 \(V, E, need\) 分别表示点数，边数和需要的白色边数。
接下来 \(E\) 行,每行 \(s, t, c, col\) 表示这边的端点（点从 \(1\) 开始标号），边权，颜色（\(0\) 白色, \(1\) 黑色）。
输出格式
一行表示所求生成树的边权和。
输入样例
3 3 1
1 2 100 1
1 3 20 0
2 3 25 0
输出样例
120
数据规模
对于 \(20\%\) 数据，\(V, E \leq 20\)。
对于另外 \(20\%\) 的数据，\(c \leq 10\)。
对于所有数据，\(V, E \leq 100000\)，\(c\) 为 \([1, 1000]\) 中的正整数。
完整代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9;
struct edge{
int u, v, c, val;
} E[N], tmp[N];
int n, m, need;
int fa[N], sum, cnt;
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool cmp(edge x, edge y){
if(x.val == y.val)
return x.c < y.c;
return x.val < y.val;
}
bool check(int x){
sum = 0, cnt = 0;
for(int i = 1; i <= n; i++)
fa[i] = i;
for(int i = 1; i <= m; i++){
tmp[i] = E[i];
if(!E[i].c)
tmp[i].val += x;
}
sort(tmp + 1, tmp + m + 1, cmp);
for(int i = 1; i <= m; i++){
int fu = find(tmp[i].u), fv = find(tmp[i].v);
if(fu != fv){
fa[fu] = fv;
sum += tmp[i].val;
cnt += !tmp[i].c;
}
}
return cnt >= need;
}
signed main(){
freopen("e2.in", "r",stdin);
freopen("e2.out", "w",stdout);
scanf("%lld%lld%lld", &n, &m, &need);
for(int i = 1; i <= m; i++)
scanf("%lld%lld%lld%lld", &E[i].u, &E[i].v, &E[i].val, &E[i].c);
int l = -1005, r = 1005, ans;
while(l < r){
int mid = (l + r) / 2;
if(check(mid)){
ans = sum - need * mid;
l = mid + 1;
} else
r = mid;
}
printf("%lld", ans);
return 0;
}
T2
题目描述
小 \(Q\) 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个 \(N \times N\) 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：
-
行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）
-
列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）
游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。对于某些关卡，小 \(Q\) 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小 \(Q\) 决定写一个程序来判断这些关卡是否有解。
输入格式
第一行包含一个整数 \(T\)，表示数据的组数。
接下来包含 \(T\) 组数据，每组数据第一行为一个整数 \(N\)，表示方阵的大小；接下来 \(N\) 行为一个 \(N * N\) 的 \(01\) 矩阵（\(0\) 表示白色，\(1\) 表示黑色）。
输出格式
输出文件应包含 \(T\) 行。对于每一组数据，如果该关卡有解，输出一行 Yes；否则输出一行 No。
输入样例
2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0
输出样例
No
Yes
数据规模
对于 \(20\%\) 的数据，\(N \leq 6\)。
对于 \(100\%\) 的数据，\(N \leq 200, T \leq 10\)。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 4e2 + 9;
int G[N][N];
int match[N], reserve_boy[N];
int a[N][N], n, T;
bool dfs(int x){
for(int i = n + 1; i <= 2 * n; i++)
if(!reserve_boy[i] && G[x][i]){
reserve_boy[i] = 1;
if(!match[i] || dfs(match[i])){
match[i] = x;
return true;
}
}
return false;
}
void init(){
memset(G, 0, sizeof(G));
memset(match, 0, sizeof(match));
memset(reserve_boy, 0, sizeof(reserve_boy));
}
int main(){
freopen("f.in", "r", stdin);
freopen("f.out", "w", stdout);
scanf("%d", &T);
while(T--){
init();
scanf("%d", &n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
scanf("%d", &a[i][j]);
if(a[i][j] == 1)
G[i][j + n] = 1;
}
int sum = 0;
for(int i = 1; i <= n; i++){
memset(reserve_boy, 0, sizeof(reserve_boy));
if(dfs(i))
sum++;
}
if(sum == n)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
T3
题目描述
有两条蛇（\(1\) 号蛇和 \(2\) 号蛇）在 \(n\) 行 \(m\) 列的地图上，地图上有障碍物。一条蛇碰到蛇身/障碍物/边界就会死。蛇身会不断长长——可以理解为蛇尾位置不会变，蛇只会向前伸展不会缩尾巴。两条蛇都绝顶聪明，如果自己能赢，一定会尽量快地赢；如果自己会输，一定会死得尽量晚。给出初始局面，两蛇轮流走，每次可以且必须向上下左右移动一格。\(1\) 号蛇先走，请告诉我谁会在多少回合时赢。
输入格式
第一行 \(2\) 个整数 \(n, m\)，表示地图有 \(n\) 行 \(m\) 列。
接下来 \(n\) 行，每行 \(m\) 个数，表示地图该位置的东西。\(0\) 表示空地，\(1, 2\) 表示两蛇蛇头位置，\(3\) 表示障碍物。(\(1, 2\) 会且只会在 \(1\) 个格子出现)
输出格式
输出一行 \(2\) 个正整数，第一个数表示谁能赢，第二个数表示在第几回合赢。
输入样例
3 3
1 0 0
3 0 3
0 0 2
输出样例
2 5
数据规模
对于 \(50\%\) 数据，\(n \leq 6, m \leq 8\)。
对于 \(100\%\) 数据，\(1 \leq n \leq 20, 1 \leq m \leq 20\)，\(0\) 的个数不超过 \(50\) 个。
T4
题目描述
\(Alice\) 和 \(Bob\) 经常利用网络传播一些不法信息。网络由 \(n\) 台电脑组成，\(Alice\) 拥有 \(1\) 号电脑，\(Bob\) 拥有 \(n\) 号电脑。有 \(m\) 对电脑间可以通过电缆单向传输信息。为了不被拦截，\(Alice\) 每次传送信息都可以选取任意一条路径（经过的电脑可以重复），把信息沿着电缆传送给 \(Bob\)。现在政府获知了这一情报，他们可以侵入恰好 \(1\) 台电脑，并获取经过这条电脑的所有信息。政府希望（无论 \(Alice\) 选择的路线如何）他们对 \(Alice\) 发送的每条信息都恰好获取 \(1\) 次（如果太少，会漏掉重要情报；如果太多，他们的电脑会被塞满的）。现在你需要求出政府可以选择入侵哪些电脑以达到要求。
输入格式
第一行一个整数 \(t\) 代表测试数据组数。
对于每组数据：第一行两个整数 \(n, m\)。接下来 \(m\) 行，每行两个整数 \(a, b\)，表示电脑 \(a\) 可以单向传递信息到电脑 \(b\)。注意 \(a\) 与 \(b\) 可能相同。每对不同的有序对 \((a, b)\) 最多只会出现一次。
输出格式
对于每组数据，先输出一行一个整数 \(k\)，代表政府可以选择入侵的电脑数目。接下来一行 \(k\) 个由空格分隔的整数，按照信息从 \(Alice\) 传递到 \(Bob\) 所经过的电脑的顺序，输出政府可以选择入侵的电脑的编号。如果信息不能从 \(Alice\) 传递到 \(Bob\)，则认为政府不用入侵任何电脑。
输入样例
4
4 3
2 4
1 3
3 2
2 2
1 2
2 1
3 1
2 3
4 4
1 2
2 4
3 4
1 3
输出样例
4
1 3 2 4
0
0
2
1 4
样例解释
在第二组数据中，由于政府不想看见重复的信息，因此他们无法入侵任何电脑。
在第三组数据中，\(Alice\) 无法将信息传送到 \(Bob\)，因此政府不用入侵任何电脑。
在第四组数据中，政府不能入侵电脑 \(2\) 或电脑 \(3\)，因为他们可能会漏掉信息。
数据规模
对于 \(30\%\) 数据，\(n \leq 1000, m \leq 3000\)。
对于 \(100\%\) 数据，\(2 \leq n \leq 500000, 0 \leq m \leq 1000000, t \leq 10\)。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9, M = 1e6 + 9;
struct Edge{
int v, nex;
} ori[M << 1], anti[M << 1], dom[M << 1];
int headori[N], headanti[N], headdom[N], oricnt, anticnt, domcnt;
void addori(int u, int v){
ori[++oricnt] = Edge{v, headori[u]};
headori[u] = oricnt;
}
void addanti(int u, int v){
anti[++anticnt] = Edge{v, headanti[u]};
headanti[u] = anticnt;
}
void adddom(int u, int v){
dom[++domcnt] = Edge{v, headdom[u]};
headdom[u] = domcnt;
}
int n, m;
int dfn_tar[N], low[N], ins[N], dfncnt_tar;
int scc[N], sc;
int sz[N];
stack <int> s;
void tarjan(int u) {
low[u] = dfn_tar[u] = ++dfncnt_tar, ins[u] = 1;
s.push(u);
for(int i = headori[u]; i; i = ori[i].nex) {
const int &v = ori[i].v;
if(!dfn_tar[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(ins[v])
low[u] = min(low[u], dfn_tar[v]);
}
if(dfn_tar[u] == low[u]){
++sc;
while(s.top() != u){
scc[s.top()] = sc;
sz[sc]++;
ins[s.top()] = 0;
s.pop();
}
scc[s.top()] = sc;
sz[sc]++;
ins[s.top()] = 0;
s.pop();
}
}
int fat[N], dfn[N], mp[N], dfncnt;
int fa[N], semi[N], idom[N], mid[N], ans;
bool flag[N];
int find(int x){
if(fa[x] == x)
return x;
int fx = fa[x], y = find(fa[x]);
if(dfn[semi[mid[fx]]] < dfn[semi[mid[x]]])
mid[x] = mid[fx];
return fa[x] = y;
}
void dfs(int u, int father){
dfn[u] = ++dfncnt;
mp[dfncnt] = u;
fat[u] = father;
for(int i = headori[u]; i; i = ori[i].nex){
int v = ori[i].v;
if(!dfn[v])
dfs(v, u);
}
}
bool vis[N], loop[N];
void calc(int u, int typ){
vis[u] = true;
if(flag[u] && sz[scc[u]] == 1 && !loop[u] && typ == 1)
printf("%d ", u);
else if(flag[u] && sz[scc[u]] == 1 && !loop[u] && typ == 0)
ans++;
for(int i = headori[u]; i; i = ori[i].nex){
int v = ori[i].v;
if(vis[v])
continue;
calc(v, typ);
}
}
void Dominate(){
for(int i = n; i >= 2; i--){
int tmp = n, u = mp[i];
for(int j = headanti[u]; j; j = anti[j].nex){
int v = anti[j].v;
if(!dfn[v])
continue;
if(dfn[v] < dfn[u])
tmp = min(tmp, dfn[v]);
else {
int fv = find(v);
tmp = min(tmp, dfn[semi[mid[v]]]);
}
}
semi[u] = mp[tmp];
fa[u] = fat[u];
adddom(semi[u], u);
u = mp[i - 1];
for(int j = headdom[u]; j; j = dom[j].nex){
int v = dom[j].v;
int fv = find(v);
if(semi[mid[v]] == u)
idom[v] = u;
else
idom[v] = mid[v];
}
}
for(int i = 2; i <= n; i++){
int v = mp[i];
if(idom[v] != semi[v])
idom[v] = idom[idom[v]];
}
memset(headdom, 0, sizeof(headdom));
domcnt = 0;
for(int i = 1; i < n; i++)
adddom(idom[i], i);
for(int i = n; ;i = idom[i]){
if(i == 0)
break;
flag[i] = true;
}
calc(1, 0);
memset(vis, 0, sizeof(vis));
printf("%d\n", ans);
if(ans == 0){
printf("\n");
return;
}
calc(1, 1);
printf("\n");
}
void init(){
memset(vis, 0, sizeof(vis));
memset(fat, 0, sizeof(fat));
memset(dfn, 0, sizeof(dfn));
memset(mp, 0, sizeof(mp));
memset(idom, 0, sizeof(idom));
memset(flag, 0, sizeof(flag));
memset(dfn_tar, 0, sizeof(dfn_tar));
memset(low, 0, sizeof(low));
memset(ins, 0, sizeof(ins));
memset(scc, 0, sizeof(scc));
memset(sz, 0, sizeof(sz));
memset(headori, 0, sizeof(headori));
memset(headanti, 0, sizeof(headanti));
memset(headdom, 0, sizeof(headdom));
memset(loop, 0, sizeof(loop));
while(!s.empty())
s.pop();
ans = dfncnt = dfncnt_tar = sc = oricnt = anticnt = domcnt = 0;
}
int T;
int main(){
freopen("i.in", "r", stdin);
freopen("i.out", "w", stdout);
scanf("%d", &T);
while(T--){
init();
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
fa[i] = semi[i] = mid[i] = i;
for(int i = 1; i <= m; i++){
int u, v;
scanf("%d%d", &u, &v);
if(u == v){
loop[u] = true;
continue;
}
addori(u, v);
addanti(v, u);
}
tarjan(1);
if(dfn_tar[n] == 0 || scc[1] == scc[n])
printf("0\n");
else {
dfs(1, 0);
Dominate();
}
}
return 0;
}