首页 > 其他分享 >CF416E 题解

CF416E 题解

时间:2024-04-13 16:13:04浏览次数:23  
标签:cnt int 题解 rep CF416E 枚举 dis define

前置知识:floyd

题意

给定一个 \(n\) 个点 \(m\) 条边的无向简单图,对于每对 \((s,t), 1 \le s < t \le n\),求出有多少条边被至少一个 \(s \to t\) 的路径经过。

\(n \le 500, m \le \frac{n(n - 1)}{2}\)

题解

首先一个很一眼的做法先 floyd 一遍求出 \(dis(i, j)\),接着枚举 \((s, t)\),然后再枚举边 \((u, v, w)\),如果有:

\[dis(s, u) + w + dis(v, t) = dis(s, t) \lor \\ dis(s, v) + w + dis(u, t) = dis(s, t) \]

那么 \((u, v, w)\) 会被 \(s \to t\) 的至少一条最短路经过,统计这种边的数量即可。时间复杂度 \(O(n^2m)\),考虑优化成 \(O(n^3)\)。

上面的做法的复杂度劣是因为枚举了边,考虑枚举一个中转点 \(p\),满足:

\[dis(s, p) + dis(p, t) = dis(s, t) \]

再考虑 \(p\) 对答案的贡献。考虑算 \(s \to p\) 的最短路的最后一条边的种类数 \(cnt_p\),则 \(p\) 对答案的贡献就是 \(cnt_p\)。对 \(cnt_p\) 的预处理方法是枚举边 \((q, p, l)\),且满足 \(dis(s, q) + l = dis(p)\),\(cnt_p\) 等于这种边的数量。

此题主要考查了对 floyd 的运用,比较关键的思维转化是枚举中转点并计算其贡献的步骤。

code:

#include <bits/stdc++.h>
#define vi vector <int>
#define vl vector <i64>
#define pii pair <int, int>
#define pll pair <i64, i64>
#define mp make_pair
#define tpi tuple <int, int, int>
#define tpl tuple <i64, i64, i64>
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define bg begin()
#define ed end()
#define sz(x) (int)(x.size())
#define alls(x) x.bg, x.ed
#define rep(i, l, r) for (int i = (l); i <= (int)(r); ++i)
#define re(i, l, r) rep(i, (l), (r) - 1)
#define per(i, r, l) for (int i = (r); i >= (int)(l); --i)
#define er(i, r, l) per(i, (r) - 1, (l))
#define repp(i, v) for (auto i : v)
#define i64 long long
#define ld long double
using namespace std;
const int inf = 1E9;
const i64 INF = 1E15;
#define int i64
const int N = 505;
int n, m, dis[N][N], cnt[N], ans[N][N], a[N * N], b[N * N], l[N * N];
signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m;
  rep(i, 1, n) rep(j, 1, n) dis[i][j] = (i == j ? 0 : INF);
  rep(i, 1, m) {
    cin >> a[i] >> b[i] >> l[i];
    dis[a[i]][b[i]] = dis[b[i]][a[i]] = l[i];
  }
  rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) {
    if (k == i || k == j || i == j) continue;
    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  }
  rep(s, 1, n) {
    fill(cnt + 1, cnt + 1 + n, 0);
    rep(i, 1, m) {
      if (dis[s][a[i]] + l[i] == dis[s][b[i]]) ++cnt[b[i]];
      if (dis[s][b[i]] + l[i] == dis[s][a[i]]) ++cnt[a[i]];
    }
    rep(t, 1, n) rep(p, 1, n) {
      if (dis[s][p] + dis[p][t] == dis[s][t])
        ans[s][t] += cnt[p];
    }
  }
  rep(i, 1, n) rep(j, i + 1, n) cout << ans[i][j] << ' ';
  return 0;
}

标签:cnt,int,题解,rep,CF416E,枚举,dis,define
From: https://www.cnblogs.com/CTHOOH/p/18131787

相关文章

  • [CF1954] Educational Codeforces Round 164 (Rated for Div. 2) 题解
    [CF1954]EducationalCodeforcesRound164(RatedforDiv.2)题解A.PaintingtheRibbon最优策略是染\(\lceil\dfrac{n}{m}\rceil\)个颜色,然后Bob会把剩下的都染成这个颜色voidwork(){intn,m,k,c;cin>>n>>m>>k;c=(n+m-1)/m;......
  • CF1618G Trader Problem 题解
    CF1618GTraderProblem题解题目链接:CF|洛谷提供一个在线做法。分析1我们不妨把\(a\)和\(b\)合并为一个序列,称合并后的序列为\(c\),并将其不降序排序。把玩样例后不难发现:对于一个物品序列\(c_1,c_2,\cdots,c_l\),满足\(\foralli<l,c_{i+1}-c_i\lek\)(即任意......
  • [CF1942] CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes! A~E 题解
    [CF1942]CodeTONRound8(Div.1+Div.2,Rated,Prizes!A~E题解A.FarmerJohn'sChallenge只有两种情况,一种是单调递增,这时\(k=1\),另一种是所有数都相同,这时\(k=n\)。B.BessieandMEX首位可以确定,然后从前往后增量构造\(p\)即可。voidwork(){cin>>......
  • CF1837E Play Fixing 题解
    首先来考虑什么情况方案数为\(0\):可以确定,在某一层中,两个原本都能晋级的队伍比赛;可以确定,在某一层中,两个原本都不能晋级的队伍比赛。发现假如写出每一场比赛及其胜者,可以形成一棵树形结构,在里面打标记即可判断是否为\(0\)。我们设\(a_i\)表示第\(i\)层新加的队伍中位......
  • [题解][2022年江西省大学生程序设计竞赛] Remove and append
    题目描述给定一个包含n个整数的数组a。定义一个操作如下:从数组a中选择k个整数,将它们删除,并将它们的和追加到数组末尾。如果数组A比数组B(长度相同)字典序大,那么在A和B第一次不同的位置上,A的数字比B对应位置上的数字要大。例如,[0,1,14,0]比[0,1,5,6]字典序大,因为它们在第三......
  • C++算法题解 - 递归实现排列型枚举 - 递归法 (图文) (递归搜索树)
    题目:递归实现排列型枚举把1∼n这n个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数n。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行相邻两个数用一个空格隔开。其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。数据......
  • [题解] [洛谷P7883] 平面最近点对(加强版)
    [洛谷P1429]平面最近点对(加强版)题目描述给定平面上的\(n\)个点,求其中距离最小的两个点之间的距离。输入格式第一行:\(n\),保证\(2\leqn\leq200000\)。接下来\(n\)行,每行两个实数:\(x,y\),表示一个点的横坐标和纵坐标,中间用一个空格隔开。输出格式仅一行,一个实数......
  • atcoder beginer 347 (abc347) D E 题解
     D就是二进制下,哪些位置有重合(两个1),哪些位置没有重合(1个1,1个0),剩下的都是0。xor的结果<2^60,就是小于60位(二进制下)。注意要有要求两个数需要是2^60,于是要有大小的判断,因为有的a,b会2^60,但是按照题目要求,这个情况不行。比如xor的结果,60位都是1,然后a、b各有60个1,那么需要有30个1......
  • atcoder beginer 348 (abc348) D E F 题解
     E非常经典的树上操作(树上DP)。父节点到某个子节点,值是如何变化的。1#include<cstdio>2#include<cstdlib>3#include<cstring>4#include<cmath>5#include<cstdbool>6#include<string>7#include<algorithm>8#include<iost......
  • 2024.4.10华为暑期实习笔试题解尝试1~2
    题目在4.10华为暑期实习笔试题解努力开摆的小鱼2024-04-10T1简单难度,按照题意顺着写就可以n=int(input())#表示计费日志的条数lst=[]#去重后的日志ss=set()#为了去重foriinrange(n):s=tuple(input().split(","))t=s[0]+s[1]+s[2]#......