• 图论 2023.11.20

    次短路

    P2829 大逃离
    题意：给定一个无向图，入口1，出口n,求第二短路的值
    一个节点所直接连接的地方小于k个（起点和终点除外），那么他就不敢进去。
    n<=5000，m<=100000
    思路：次短路为某一条边的长度+起点到该边一条端点的最短路+终点到另一条边的最短路
    spfa跑从起点，从终点的最短路，之后枚举所有的边，连接点的记录可能有重边用vis标记
     

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. #define fr(i,z,n) for(int i = z;i <= n; i++)
    7. #define fer(i,x)   for(int i=e.head[x];i;i=e.next[i])
    8. const int N = 5002, M = 100002, INF = 1e9 + 7;
    9. int n, m, k, mindist, secdist = INF;//mindist最短路,secdist次短路
    10. int  t[N], dist[2][N];//t是每个点的出边数
    11. bool used[N], vis[N];
    12. template<size_t size>
    13. struct Road {
    14.     int to[size], next[size], head[size], cnt = 1;
    15.     int w[size];
    16.     void add(int x, int y, int ww) {
    17.         to[cnt] = y;
    18.         w[cnt] = ww;
    19.         next[cnt] = head[x];
    20.         head[x] = cnt++;
    21.     }
    22.     void clear(int n) {
    23.         for (int i = 0; i <= n; i++) {
    24.             head[i] = 0;
    25.         }
    26.         cnt = 1;
    27.     }
    28. };
    29. Road<(100010<<1)>e;
    30. void SPFA(int S, int op)//op=0是起点的参数,op=1是终点的参数
    31. {
    32.     for (int i = 1; i <= n; i++) {
    33.         dist[op][i] = INF, used[i] = 0;
    34.     }
    35.     queue<int> Q;
    36.     Q.push(S);
    37.     used[S] = 1;
    38.     dist[op][S] = 0;
    39.     while (!Q.empty()){
    40.         int now = Q.front(); 
    41.         Q.pop();
    42.         used[now] = 0;
    43.         fer(i,now){
    44.             int v = e.to[i];
    45.             int w = e.w[i];
    46.             if (dist[op][now] +w < dist[op][v] && t[v] >= k)//筛掉不合法的(即小于k的)
    47.             {
    48.                 dist[op][v] = dist[op][now] + w;
    49.                 if (!used[v]) { Q.push(v); used[v] = 1; }
    50.             }
    51.         }
    52.     }
    53. }
    54. int main() {
    55.     scanf("%d%d%d", &n, &m, &k);
    56.     for (int i = 1; i <= m; i++) {
    57.         int u, v, w;
    58.         scanf("%d%d%d", &u, &v, &w);
    59.         e.add(u, v, w);
    60.         e.add(v, u, w);
    61.     }
    62.     fr(i, 1, n) {          //记录每一个节点的连接点数
    63.         memset(vis, 0, sizeof(vis));
    64.         fer(j, i) {
    65.             int v = e.to[j];
    66.             if (!vis[v]) {               //防止重边，自环也算
    67.                 t[i]++;
    68.                 vis[v] = 1;
    69.             }
    70.         }
    71.     }
    72.     t[1] = INF; t[n] = INF;      //起点与终点不包括
    73.     SPFA(1, 0);
    74.     SPFA(n, 1);
    75.     mindist = dist[0][n];
    76.     for (int i = 1; i <= n; i++) {    //枚举所有边
    77.         if (t[i] < k)continue;
    78.         fer(j, i) {{
    79.                 int v = e.to[j];
    80.                 int len = dist[0][i] + e.w[j] + dist[1][v];
    81.                 if (len > mindist && t[v] >= k)secdist = min(secdist, len);
    82.             }
    83.         }
    84.     }
    85.     printf("%d\n", secdist >= INF ? -1 : secdist);
    86.     return 0;
    87. }

    单源最短路->多源最短路

    P5304 [GXOI/GZOI2019] 旅行者(单源最短路->多源最短路)
    题意：给定一个有向图，求给定的k个城市的两两城市间最短路的最小值
    n<=1e5,m<=5e5,k<=n
    思路：两遍dijkstra,
    第一次将所有给定点的点加入到队列,(相当于从所有给定点出发到其他点的最短路)
    于是需要维护两个东西。1.最短路的距离，2到当前点的最短路的起点(相当于染色操作)
    第二次建立反图，同样将所有给定点的点加入到队列，求出其他点到给定点的最短路
    同样维护两个东西。1.最短路的距离，2最短路对应的终点
    遍历每一条边当起点!=终点(自环)时，更新答案
     

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #define endl '\n'
    13. #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    14. #define ms(x,y) memset(x,y,sizeof x);
    15. #define YES cout<<"YES"<<'\n';
    16. #define NO  cout<<"NO"<<'\n';
    17. #define fr(i,z,n) for(int i = z;i <= n; i++)
    18. #define fer(i,x)   for(int i=e.head[x];i;i=e.next[i])
    19. #define fer1(i,x)   for(int i=e1.head[x];i;i=e1.next[i])
    20. #define ufr(i,n,z) for(int i = n;i >= z; i--)
    21. #define int long long
    22. typedef long long ll;
    23. const ll N = 2e5 + 10, inf = 1e18;
    24. const ll mod = 1e9 + 7;
    25. using namespace std;
    26. template<size_t size>
    27. struct Road {
    28.     int to[size], next[size], head[size], cnt = 1;
    29.     ll w[size];
    30.     void add(int x, int y, ll ww) {
    31.         to[cnt] = y;
    32.         w[cnt] = ww;
    33.         next[cnt] = head[x];
    34.         head[x] = cnt++;
    35.     }
    36.     void clear(int n) {
    37.         for (int i = 0; i <= n; i++) {
    38.             head[i] = 0;
    39.         }
    40.         cnt = 1;
    41.     }
    42. };
    43. Road<(500010)>e;
    44. Road<(500010)>e1;
    45. int a[N];
    46. int dis1[N], dis2[N];
    47. int col1[N], col2[N];
    48. bool vis[N];
    49. int n, m, k;
    50. void dijkstra1() {
    51.     fr(i, 1, n) {
    52.         dis1[i] = inf;
    53.         vis[i] = 0;
    54.     }
    55.     priority_queueint, int>, vectorint, int> >, greaterint, int> > > q;
    56.     fr(i, 1, k) {
    57.         q.push({ 0,a[i] });
    58.         dis1[a[i]] = 0;
    59.         col1[a[i]] = a[i];
    60.     }
    61.     while (!q.empty()) {
    62.         int x = q.top().second;
    63.         q.pop();
    64.         if (vis[x]) {
    65.             continue;
    66.         }
    67.         vis[x] = 1;
    68.         fer(i, x) {
    69.             int v = e.to[i];
    70.             int w = e.w[i];
    71.             if (dis1[x] + w < dis1[v]) {
    72.                 dis1[v] = dis1[x] + w;
    73.                 q.push({ dis1[v],v });
    74.                 col1[v] = col1[x];                 //染色,标记起点
    75.             }
    76.         }
    77.     }
    78. }
    79. void dijkstra2() {
    80.     fr(i, 1, n) {
    81.         dis2[i] = inf;
    82.         vis[i] = 0;
    83.         col2[i] = 0;
    84.     }
    85.     priority_queueint, int>, vectorint, int> >, greaterint, int> > > q;
    86.     fr(i, 1, k) {
    87.         q.push({ 0,a[i] });
    88.         dis2[a[i]] = 0;
    89.         col2[a[i]] = a[i];
    90.     }
    91.     while (!q.empty()) {
    92.         int x = q.top().second;
    93.         q.pop();
    94.         if (vis[x]) {
    95.             continue;
    96.         }
    97.         vis[x] = 1;
    98.         fer1(i, x) {
    99.             int v = e1.to[i];
    100.             int w = e1.w[i];
    101.             if (dis2[x] + w < dis2[v]) {
    102.                 dis2[v] = dis2[x] + w;
    103.                 q.push({ dis2[v],v });
    104.                 col2[v] = col2[x];                 //染色,标记起点
    105.             }
    106.         }
    107.     }
    108. }
    109. void solve() {
    110.     cin >> n >> m >> k;
    111.     e.clear(n);
    112.     e1.clear(n);
    113.     vectorint, 3>>ve;
    114.     fr(i, 1, n) {
    115.         col1[i] = 0;
    116.         col2[i] = 0;
    117.     }
    118.     fr(i, 1, m) {
    119.         int u, v, w;
    120.         cin >> u >> v >> w;
    121.         e.add(u, v, w);             //有向图
    122.         e1.add(v, u, w);
    123.         ve.push_back({ u,v,w });
    124.     }
    125.     fr(i, 1, k) {
    126.         cin >> a[i];
    127.     }
    128.     dijkstra1();
    129.     dijkstra2();
    130.     int ans = inf;
    131.     for (auto it : ve) {                     //遍历所有的边
    132.         int u = it[0];
    133.         int v = it[1];
    134.         int w = it[2];
    135.        // cout << u << ' ' << v << ' ' << col1[u] << ' ' << col2[v] << '\n';
    136.         if ((col1[u]&&col2[v]) && col1[u] != col2[v]) {
    137.            // cout << "YES" << '\n';
    138.             ans = min(ans, dis1[u] + dis2[v]+w);
    139.         }
    140.     }
    141.     cout << ans << '\n';
    142. }
    143.  
    144. signed main()
    145. {
    146.     ios;
    147.     int t = 1;
    148.     cin >> t;
    149.     while (t--) {
    150.         solve();
    151.     }
    152. }

    割点+联通块

    P3469 [POI2008] BLO-Blockade
    给定一个无向图(图是联通的)，无重边，对于每个节点求出去与节点i关联的所有边去掉以后(不去掉节点i本身),
    无向图有多少个有序点(x, y)，满足x 和y 不连通。
    n<=1e5,m<=5e5
    讨论要删的点是不是割点：
    1.非割点,则为2*(n-1)
    2.割点,导致变成多个联通块，不同联通块不可相互到达，
    假设割后产生2个的联通块，大小为a,b,则贡献为2ab+2(n-1),
    假设产生k联通块2(n-1)+2∑(1<=i<=k)∑(1<=j<=k,j!=i)sizei*sizej
    会超时，∑(1<=j<=k,j!=i)sizej优化为n-sizei-1
    于是变为2∑(1<=i<=k)sizei*(n-sizei-1)
    转为求联通块大小问题
    再dfs的过程中用sum防止重复计算的
     

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #define int long long
    7. const int N = 5e5 + 10;
    8. using namespace std;
    9. vector<int> edges[N];
    10. vector<int> edges2[N];
    11. stack<int>stk;
    12. int dfsn[N], low[N], instk[N], cnt;
    13. int n, m;
    14. int ans[N], Size[N];
    15. int tot;
    16. void tarjan(int p){
    17.     low[p] = dfsn[p] = ++cnt;
    18.     instk[p] = 1;
    19.     Size[p] = 1; 
    20.     int sum = 0;
    21.     stk.push(p); // 进栈
    22.     for (auto q : edges[p]) {
    23.         if (!dfsn[q]) { // 未访问过
    24.             tarjan(q); // 递归地搜索
    25.             Size[p] += Size[q];       //子树的大小            
    26.             if (low[q] >= dfsn[p]) {  // p为割点满足low[q] >= dfsn[p]
    27.                 ans[p] += Size[q] *(sum);   //以p为子树的贡献点
    28.                 sum += Size[q];
    29.             } 
    30.             low[p] = min(low[p], low[q]);
    31.         }
    32.         else {
    33.             low[p] = min(low[p], dfsn[q]);
    34.         }
    35.     }
    36.     ans[p] += (n - sum - 1) * sum;//剩下的点产生的贡献！
    37.     ans[p] += n - 1;
    38. }
    39. signed main() {
    40.     cin >> n >> m;
    41.     for (int i = 1; i <= m; i++) {
    42.         int x, y;
    43.         cin >> x >> y;
    44.         edges[x].push_back(y);
    45.         edges[y].push_back(x);
    46.     }
    47.     for (int i = 1; i <= n; ++i)
    48.         if (!dfsn[i])
    49.             tarjan(i);
    50.     for (int i = 1; i <= n; i++) {
    51.         cout << 2*ans[i] << '\n';
    52.     }
    53. }

  • 相关阅读:
    【小迪安全2023】第57天:服务攻防-应用协议&Rsync&SSH&RDP&FTP&漏洞批扫&口令猜解
    2023牛客暑假多校第四场（补题向题解：J）
    2. ESP8266通过I2C控制OLED显示
    微内核操作系统
    React_react入门
    TMC5160问题，插上步进电机、步进电机一转或步进电机带负载转瞬间，TMC5160就无输出
    数据结构-线性表
    六、【React拓展】Component的2个效率问题
    Linux 软件安装（基于RPM）。
    vue3 自定义loading
  • 原文地址：https://blog.csdn.net/m0_75027890/article/details/134498542