10.5下午总结

kamikuQAQ · 2025-10-05 20:21:22 · 个人记录

T1

纯送存入起点然后跑bfs一圈一圈染色然后取最小值就行

#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

由于是树上问题，两点之间只有唯一路径没有最短路，将两点之间的距离列成式就变为了

对应成三个点就变成了

题目中说了两点之间距离要%2，所以答案变成了

然后列出等式，同时减dis[i]mod2+dis[j]mod2+dis[k]mod2
得dis[i]%2=dis[j]%2=dis[k]%2
所以我们只需要统计图中1和0的数量然后排列组合就行

#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到最短路兴趣点来源

#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;
}