图论 2023.11.20

次短路

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

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define fr(i,z,n) for(int i = z;i <= n; i++)
#define fer(i,x)   for(int i=e.head[x];i;i=e.next[i])
const int N = 5002, M = 100002, INF = 1e9 + 7;
int n, m, k, mindist, secdist = INF;//mindist最短路,secdist次短路
int  t[N], dist[2][N];//t是每个点的出边数
bool used[N], vis[N];
template<size_t size>
struct Road {int to[size], next[size], head[size], cnt = 1;int w[size];void add(int x, int y, int ww) {to[cnt] = y;w[cnt] = ww;next[cnt] = head[x];head[x] = cnt++;}void clear(int n) {for (int i = 0; i <= n; i++) {head[i] = 0;}cnt = 1;}
};
Road<(100010<<1)>e;
void SPFA(int S, int op)//op=0是起点的参数,op=1是终点的参数
{for (int i = 1; i <= n; i++) {dist[op][i] = INF, used[i] = 0;}queue<int> Q;Q.push(S);used[S] = 1;dist[op][S] = 0;while (!Q.empty()){int now = Q.front(); Q.pop();used[now] = 0;fer(i,now){int v = e.to[i];int w = e.w[i];if (dist[op][now] +w < dist[op][v] && t[v] >= k)//筛掉不合法的(即小于k的){dist[op][v] = dist[op][now] + w;if (!used[v]) { Q.push(v); used[v] = 1; }}}}
}
int main() {scanf("%d%d%d", &n, &m, &k);for (int i = 1; i <= m; i++) {int u, v, w;scanf("%d%d%d", &u, &v, &w);e.add(u, v, w);e.add(v, u, w);}fr(i, 1, n) {          //记录每一个节点的连接点数memset(vis, 0, sizeof(vis));fer(j, i) {int v = e.to[j];if (!vis[v]) {               //防止重边，自环也算t[i]++;vis[v] = 1;}}}t[1] = INF; t[n] = INF;      //起点与终点不包括SPFA(1, 0);SPFA(n, 1);mindist = dist[0][n];for (int i = 1; i <= n; i++) {    //枚举所有边if (t[i] < k)continue;fer(j, i) {{int v = e.to[j];int len = dist[0][i] + e.w[j] + dist[1][v];if (len > mindist && t[v] >= k)secdist = min(secdist, len);}}}printf("%d\n", secdist >= INF ? -1 : secdist);return 0;
}

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

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

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#include<array>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\n';
#define NO  cout<<"NO"<<'\n';
#define fr(i,z,n) for(int i = z;i <= n; i++)
#define fer(i,x)   for(int i=e.head[x];i;i=e.next[i])
#define fer1(i,x)   for(int i=e1.head[x];i;i=e1.next[i])
#define ufr(i,n,z) for(int i = n;i >= z; i--)
#define int long long
typedef long long ll;
const ll N = 2e5 + 10, inf = 1e18;
const ll mod = 1e9 + 7;
using namespace std;
template<size_t size>
struct Road {int to[size], next[size], head[size], cnt = 1;ll w[size];void add(int x, int y, ll ww) {to[cnt] = y;w[cnt] = ww;next[cnt] = head[x];head[x] = cnt++;}void clear(int n) {for (int i = 0; i <= n; i++) {head[i] = 0;}cnt = 1;}
};
Road<(500010)>e;
Road<(500010)>e1;
int a[N];
int dis1[N], dis2[N];
int col1[N], col2[N];
bool vis[N];
int n, m, k;
void dijkstra1() {fr(i, 1, n) {dis1[i] = inf;vis[i] = 0;}priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;fr(i, 1, k) {q.push({ 0,a[i] });dis1[a[i]] = 0;col1[a[i]] = a[i];}while (!q.empty()) {int x = q.top().second;q.pop();if (vis[x]) {continue;}vis[x] = 1;fer(i, x) {int v = e.to[i];int w = e.w[i];if (dis1[x] + w < dis1[v]) {dis1[v] = dis1[x] + w;q.push({ dis1[v],v });col1[v] = col1[x];                 //染色,标记起点}}}
}
void dijkstra2() {fr(i, 1, n) {dis2[i] = inf;vis[i] = 0;col2[i] = 0;}priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;fr(i, 1, k) {q.push({ 0,a[i] });dis2[a[i]] = 0;col2[a[i]] = a[i];}while (!q.empty()) {int x = q.top().second;q.pop();if (vis[x]) {continue;}vis[x] = 1;fer1(i, x) {int v = e1.to[i];int w = e1.w[i];if (dis2[x] + w < dis2[v]) {dis2[v] = dis2[x] + w;q.push({ dis2[v],v });col2[v] = col2[x];                 //染色,标记起点}}}
}
void solve() {cin >> n >> m >> k;e.clear(n);e1.clear(n);vector<array<int, 3>>ve;fr(i, 1, n) {col1[i] = 0;col2[i] = 0;}fr(i, 1, m) {int u, v, w;cin >> u >> v >> w;e.add(u, v, w);             //有向图e1.add(v, u, w);ve.push_back({ u,v,w });}fr(i, 1, k) {cin >> a[i];}dijkstra1();dijkstra2();int ans = inf;for (auto it : ve) {                     //遍历所有的边int u = it[0];int v = it[1];int w = it[2];// cout << u << ' ' << v << ' ' << col1[u] << ' ' << col2[v] << '\n';if ((col1[u]&&col2[v]) && col1[u] != col2[v]) {// cout << "YES" << '\n';ans = min(ans, dis1[u] + dis2[v]+w);}}cout << ans << '\n';
}signed main()
{ios;int t = 1;cin >> t;while (t--) {solve();}
}

割点+联通块

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防止重复计算的
 

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
#define int long long
const int N = 5e5 + 10;
using namespace std;
vector<int> edges[N];
vector<int> edges2[N];
stack<int>stk;
int dfsn[N], low[N], instk[N], cnt;
int n, m;
int ans[N], Size[N];
int tot;
void tarjan(int p){low[p] = dfsn[p] = ++cnt;instk[p] = 1;Size[p] = 1; int sum = 0;stk.push(p); // 进栈for (auto q : edges[p]) {if (!dfsn[q]) { // 未访问过tarjan(q); // 递归地搜索Size[p] += Size[q];       //子树的大小            if (low[q] >= dfsn[p]) {  // p为割点满足low[q] >= dfsn[p]ans[p] += Size[q] *(sum);   //以p为子树的贡献点sum += Size[q];} low[p] = min(low[p], low[q]);}else {low[p] = min(low[p], dfsn[q]);}}ans[p] += (n - sum - 1) * sum;//剩下的点产生的贡献！ans[p] += n - 1;
}
signed main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;edges[x].push_back(y);edges[y].push_back(x);}for (int i = 1; i <= n; ++i)if (!dfsn[i])tarjan(i);for (int i = 1; i <= n; i++) {cout << 2*ans[i] << '\n';}
}