2022“杭电杯” 中国大学生算法设计超级联赛(10)1 4题解
1001-Winner Prediction
题目大意:
一场比赛两个人之间进行,赢的人加一分,目前已知一些结束比赛的结果,还剩下若干场没有进行的比赛,且每场比赛的两个玩家已知。问1号玩家是否有可能成为分数最高的玩家(并列也算)。
思路:
一开始想的是贪心,未开始的比赛,如果有1号玩家参与,就让1号玩家赢,否则每次选一个分数最高的玩家,在他的所有比赛中选一场对手分数最低的比赛,让分数低的玩家赢。但是这样的贪心无法证明是正确的。
后来也想过用网络流,但是因为太久没用过了,有些生疏,没有把图建起来。赛后看题解果然也是用网络流做的。
建图的方式:
源点向每场比赛连一条容量为1的边。
每场比赛向两位选手各连一条容量为1的边。
每位选手向汇点连一条边,容量为1号玩家分数 - 自己当前的分数。
然后套板子跑最大流即可。如果汇点的流量为比赛的场数,说明有解。
AC代码:
#include <bits/stdc++.h>
#define M 20005
#define N 2005
#define mem(a, v) memset(a, v, sizeof(a))
#define inf 0x3f3f3f3f
using namespace std;
struct edge
{
int to, next;
int cap;
} e[M];
int head[N], ecnt = 1;
int dep[N], cur[N], S, T, tot;
void add(int u, int v, int cap)
{
e[++ecnt] = edge{v, head[u], cap};
head[u] = ecnt;
e[++ecnt] = edge{u, head[v], 0};
head[v] = ecnt;
}
bool bfs()
{
for (int i = 1; i <= tot; i++)
dep[i] = 0, cur[i] = head[i];
dep[S] = 1;
queue<int> q;
q.push(S);
while (q.size())
{
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (dep[v] || !e[i].cap) continue; //已经访问过或者没有残余流量,也算弧优化的一种
q.push(v);
dep[v] = dep[u] + 1;
}
}
return dep[T] != 0; //如果T点无法到达说明没有增广路了
}
int dfs(int u, int flow)
{
if (u == T || flow == 0) return flow;
int out = 0;
for (int &i = cur[u]; i; i = e[i].next)
{
int v = e[i].to;
if (dep[u] + 1 != dep[v] || !e[i].cap) continue;
int delta = dfs(v, min(flow, e[i].cap));
// if (!delta) continue; // delta==0说明不是增广路
flow -= delta;
out += delta;
e[i].cap -= delta; //正向边减去流量
e[i ^ 1].cap += delta; //反向边加流量
if (flow == 0) break;
}
return out;
}
int Dinic()
{
int maxflow = 0;
while (bfs())
maxflow += dfs(S, 1e9 + 7);
return maxflow;
}
int sc[505];
void solve()
{
int n, m1, m2, u, v, f;
cin >> n >> m1 >> m2;
mem(head, 0), mem(sc, 0);
S = ecnt = 1;
T = n + m2 + 1;
while (m1--)
{
cin >> u >> v >> f;
f ? sc[u]++ : sc[v]++;
}
for (int i = m2; i >= 1; i--)
{
cin >> u >> v;
if (u == 1 || v == 1)
sc[1]++, m2--;
else
{
add(S, i + n, 1); //源点向比赛连一条容量1的边
add(i + n, u, 1); //比赛向两个选手各连一条容量1的边
add(i + n, v, 1);
}
}
for (int i = 2; i <= n; i++)
{
if (sc[1] < sc[i])
{
cout << "NO\n";
return;
}
add(i, T, sc[1] - sc[i]);
}
if (Dinic() == m2)
cout << "YES\n";
else
cout << "NO\n";
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
1004-Average Replacement
题目大意:
给定一若干个点和若干条边,每个点有一个点权。每次操作可以选一个点,将其点权替换为其所连接的点的点权加上自己点权的平均值。经过无数次操作后输出每个点的点权。
思路:
可以肯定的是,一个连通分量里的所有点最后都会变成一个值。
猜测这个值就等于每个点的点权乘上(度数+1)的和再除以(度数+1)和。
至于为什么猜加1,因为只有一个点的连通分量时点的度数为0,所以要加1。
代入几个简单的图暴力验证一下即可。
这题比较卡常,即使是std也要跑2/3的时限,因此对细节要求比较多。
AC代码:
#include <bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;
long long dsum[N], psum[N], deg[N], p[N];
int fa[N];
int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); }
void solve()
{
int u, v, n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &p[i]);
deg[i] = 1; //初始化为1,后面就不用进行加1操作了
fa[i] = i;
dsum[i] = psum[i] = 0;
}
while (m--)
{
scanf("%d%d", &u, &v);
deg[u]++;
deg[v]++;
int fu = Find(u);
int fv = Find(v);
if (fu != fv) fa[fu] = fa[fv];
}
for (int i = 1; i <= n; i++)
{
int fi = Find(i);
dsum[fi] += deg[i];
psum[fi] += p[i] * deg[i];
}
for (int i = 1; i <= n; i++)
{
int fi = Find(i);
printf("%.6lf\n", (double)psum[fi] / dsum[fi]);
}
}
signed main()
{
int T;
scanf("%d", &T);
while (T--)
solve();
return 0;
}