专栏文章

10.5下午总结

kkamikuQAQ
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minou8yz
此快照首次捕获于
2025/12/02 05:55
3 个月前
此快照最后确认于
2025/12/02 05:55
3 个月前
查看原文

T1

纯送存入起点然后跑bfs一圈一圈染色然后取最小值就行
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a;
const int maxn = 501;
struct Node{
	int x,y;
};
queue<Node>Q;
int dis[maxn][maxn];
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
bool vis[maxn][maxn];
bool check(int x,int y) {
	if(x>=1&&x<=n&&y>=1&&y<=m) {
		return 1;
	}
	return 0;
}
void bfs() {
	while(!Q.empty()) {
		Node u=Q.front();
		Q.pop();
		for(int i=0;i<4;i++) {//开始染色
			int dxx=dx[i]+u.x,dyy=dy[i]+u.y;
			if(check(dxx,dyy)) {//无论如何，只要能优化就松弛一遍
				dis[dxx][dyy]=min(dis[dxx][dyy],dis[u.x][u.y]+1);
				if(!vis[dxx][dyy]) {//只有第一次才入队
					vis[dxx][dyy]=1;
					Q.push({dxx,dyy});
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("T1.in","r",stdin);
//	freopen("T1.out","w",stdout);
	memset(dis,0x3f,sizeof(dis));
	cin>>n>>m>>a;
	for(int i=1;i<=a;i++) {
		int x,y;
		cin>>x>>y;
		Q.push({x,y});
		dis[x][y]=0;
	}
	bfs();
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cout<<dis[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

T2

由于是树上问题，两点之间只有唯一路径没有最短路，将两点之间的距离列成式就变为了
dis(u,v)=dis[u]+dis[v]−2∗dis[lca(u,v)]dis(u,v)=dis[u]+dis[v]-2*dis[lca(u,v)]
对应成三个点就变成了
dis(i,j)=dis[i]+dis[j]−2∗dis[lca(i,j)]dis(i,j)=dis[i]+dis[j]-2*dis[lca(i,j)] dis(i,k)=dis[i]+dis[k]−2∗dis[lca(i,k)]dis(i,k)=dis[i]+dis[k]-2*dis[lca(i,k)] dis(k,j)=dis[j]+dis[k]−2∗dis[lca(j,k)]dis(k,j)=dis[j]+dis[k]-2*dis[lca(j,k)]
题目中说了两点之间距离要%2，所以答案变成了
dis(i,j)=dis[i]mod2+dis[j]mod2dis(i,j)=dis[i]mod2+dis[j]mod2
dis(i,k)=dis[i]mod2+dis[k]mod2dis(i,k)=dis[i]mod2+dis[k]mod2
dis(k,j)=dis[j]mod2+dis[k]mod2dis(k,j)=dis[j]mod2+dis[k]mod2
然后列出等式，同时减dis[i]mod2+dis[j]mod2+dis[k]mod2dis[i]mod2+dis[j]mod2+dis[k]mod2
得dis[i]dis[i]%2=dis[j]dis[j]%2=dis[k]dis[k]%2
所以我们只需要统计图中1和0的数量然后排列组合就行
CPP
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 7;
int dp[maxn];
struct Node{
    int v, w;
};
vector<Node> g[maxn];
void add_edge(int u, int v, int w){
    g[u].push_back({v, w});
    g[v].push_back({u, w});
    return;
}
int n;
void dfs(int u, int fa){
    for (int i = 0; i < g[u].size(); i++){
        int v = g[u][i].v;
        int w = g[u][i].w;
        if (v != fa){
            dp[v] = (dp[u] + w) % 2;
            dfs(v, u);
        }
    }
    return;
}
void solve(){
    cin >> n;
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }
    for (int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        w %= 2;
        add_edge(u, v, w);
    }
    dfs(1, 0);
    int cnt1, cnt0;
    cnt1 = cnt0 = 0;
    for (int i = 1; i <= n; i++){
        cnt1 += (dp[i] == 1);
        cnt0 += (dp[i] == 0);
    }
    long long ans = 1ll * cnt1 * cnt1 * cnt1 + 1ll * cnt0 * cnt0 * cnt0;
    cout << ans << "\n";
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        solve();
    }
    return 0;
}

T3

本题要跑两次最短路
首先我们需要知道，对答案来说，两个兴趣城市之间不可能存在其他的兴趣城市会成为答案的一部分，而由于m的数据范围不大，所以可以枚举u,v比枚举兴趣点更快
离边最近的兴趣点是𝑠1和𝑠2
由图可知对应的最短路是𝑑𝑖𝑠(𝑠1,𝑢)+w(𝑢,𝑣)+𝑑𝑖𝑠(𝑣,𝑠2)
然后我们将兴趣城市存起来去跑第一次dij，维护每个兴趣城市中互相的最短路，dis1[i]表示到第i个兴趣城市的最短路，col1[i]用来记录第i个兴趣城市能到的路径最短线段城市
然后我们去找其他可行的边去跑第二遍dij去优化路径，注意要建反图优化时间，所得的col2[i]就是最优路径，dis2指代优化后的城市之间最短路径
注:1、有三重情况，s1直通s2,s1经过一个点通向s2，s1经过边u,v通向s2，都已经涵盖在里面了
2、有可能出现有环的情况，使s1,s2在环上，所以用col记录最短路兴趣点的来源判环，跑了两次dij所以用两个数组分别记录col[i]即i到最短路兴趣点来源
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5+10;
int u[maxn],v[maxn],w[maxn],f[maxn];
int col1[maxn],col2[maxn];
int vis1[maxn],vis2[maxn];
int dis1[maxn],dis2[maxn];
int n,m,k;
struct Node{
	int v,w;
	bool operator<(const Node &rhs) const{
		return w>rhs.w;
	}
}; 
vector<Node>g[maxn],g2[maxn];
void dijkstra() {
	priority_queue<Node>Q;
	memset(vis1,0,sizeof(vis1));
	for(int i=1;i<=n;i++) {
		dis1[i]=1e18;
	}
	for(int i=1;i<=k;i++) {
		Q.push({f[i],0ll});
		dis1[f[i]]=0;
		col1[f[i]]=f[i];
	}
	while(!Q.empty()) {
		int u=Q.top().v;
		Q.pop();
		if(vis1[u]) {
			continue;
		}
		vis1[u]=1;
		for(int i=0;i<g[u].size();i++) {
			int v=g[u][i].v;
			if(dis1[v]>dis1[u]+g[u][i].w) {
				dis1[v]=dis1[u]+g[u][i].w;
				col1[v]=col1[u];
				Q.push({v,dis1[v]});
			}
		}
	}
}
void dijkstra2() {
	priority_queue<Node>Q;
	memset(vis2,0,sizeof(vis1));
	for(int i=1;i<=n;i++) {
		dis2[i]=1e18;
	}
	for(int i=1;i<=k;i++) {
		Q.push({f[i],0ll});
		dis2[f[i]]=0;
		col2[f[i]]=f[i];
	}
	while(!Q.empty()) {
		int u=Q.top().v;
		Q.pop();
		if(vis2[u]) {
			continue;
		}
		vis2[u]=1;
		for(int i=0;i<g2[u].size();i++) {
			int v=g2[u][i].v;
			if(dis2[v]>dis2[u]+g2[u][i].w) {
				dis2[v]=dis2[u]+g2[u][i].w;
				col2[v]=col2[u];
				Q.push({v,dis2[v]});
			}
		}
	}
}
signed main() {
	int T;
	cin>>T;
	while(T--) {
		cin>>n>>m>>k;
		for(int i=1;i<=m;i++) {
			cin>>u[i]>>v[i]>>w[i];
			g[u[i]].push_back({v[i],w[i]});
		}
		for(int i=1;i<=k;i++) {
			cin>>f[i];
		}
		dijkstra();
		for(int i=1;i<=m;i++) {
			g2[v[i]].push_back({u[i],w[i]});
		}
		dijkstra2();
		int ans=2e18;
		for(int i=1;i<=m;i++) {
			if(col1[u[i]]&&col2[v[i]]&&col1[u[i]]!=col2[v[i]]) {
				ans=min(ans,dis1[u[i]]+dis2[v[i]]+w[i]);
			}
		}
		cout<<ans<<'\n';
		for(int i=1;i<=m;i++) {
			g[u[i]].clear();
			g2[v[i]].clear();
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...