头像

氘爸-wt


访客:7190

离线:13小时前


活动打卡代码 AcWing 521. 运输计划

题目描述

一棵树,有边权,树上有若干条链,找某一条边长设为0,
可以让新的最长链的长度最小,求这个最小值。
点和链的个数上限在30万

样例


算法1

(暴力枚举) $O(nm)$

尝试树上每一条边的边长临时设为0,统计每条链的长度的最大值,
用于刷新答案的最小值。
考虑该边是否在某条链上,这个询问也是很难处理的。
还有,30万的规模明显不现实。


算法2

(二分答案) $O(nlogn)$

30万,常数不控制好,会超时1个点
二分这个最小值mid,看是否可以满足条件。
将长度超过mid的链标记出来,利用树上差分(边权)(需要dfs),
将公共边找出来,要设为0的边肯定在公共边上,
否则没有被影响到的链长度不变,还是大于mid,肯定是不行的,
换句话说,若找不到公共边则check为false;
若存在公共边(肯定在初始最长链上,而且肯定是连续的若干条边),
则找其中最长的一条边,让最长链减去该值,看结果是否小于等于mid,
若可以,则check为true(因为最长的减去该值都已经满足了,
其他更小一点的肯定也能满足),
否则check为false。
这个过程中dfs的O(n)是不能避免的,每条链的端点为树上差分标记O(m)
二分是O(max)
总计O(nlogn)

//因为采用dfsn递归求解树上差分的前缀和,效率低,所以过了19/20个点,后面程序改进了可以全过 
#include<bits/stdc++.h>
#define fi first
#define se second
#define si size()
#define UI unsigned int
using namespace std;
const int N = 3e5+10, M = 20;    
vector<pair<int, int> > a[N];   //原始边 
int b[N], d[N], fadis[N], f[N][M];  //距根长度, 深度, 与父结点距离, 倍增数组 
struct Info{
    int x, y, cofa, nodes, len; //最近公共祖先,两点之间的点数、长度 
}edge[N];                   //原始链起点终点及求得数据 
int treesub[N];             //树上差分(边权)及前缀和 
int n, m;
void dfs(int x, int fa){
    for(UI i = 0; i < a[x].si; i++){
        int y = a[x][i].fi, z = a[x][i].se;
        if(y == fa) continue;
        b[y] = b[x] + z, d[y] = d[x] + 1;   //距根长度、深度(根的深度为0) 
        fadis[y] = z;       //父结点距离 
        f[y][0] = x;
        for(int j = 1; j < M; j++){
            f[y][j] = f[f[y][j-1]][j-1];
        }               //更新倍增数组,为求lca准备 
        dfs(y, x);
    }
}
int lca(int x, int y){
    if(d[x] < d[y]) swap(x, y);
    for(int i = M-1; i >= 0; i--){
        if(d[f[x][i]] >= d[y]) x = f[x][i];
    }
    if(x == y) return x;
    for(int i = M-1; i >= 0; i--){
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}
bool Mycomp(const Info&a, const Info&b){
    return a.len > b.len;
}

void dfsn(int x, int fa){               //树上差分(边权)的前缀和,表示该边被若干条链经过 
    for(UI i = 0; i < a[x].si; i++){
        int y = a[x][i].fi, z = a[x][i].se;
        if(y == fa) continue;
        dfsn(y, x);
        treesub[x] += treesub[y];       //y的子树前缀和累计至父结点x上 
    }   
}
bool check(int va){                     //如果答案是va,看是否能够满足,需要将链长超过va的链的公共边找出来 
    memset(treesub, 0, sizeof(treesub));    
    int comnums = 0;                    //有comnums条链长超过va,树上差分(边权) 
    for(int i = 1; i <= m && edge[i].len > va; i++){
        comnums = i;
        int x = edge[i].x, y = edge[i].y, z = edge[i].cofa;
        treesub[x]++, treesub[y]++, treesub[z] -= 2;    //树上差分(边权),记录该边被经过的次数 
    }
    dfsn(1, 0);             //求前缀和 
    for(int i = 1; i <= n; i++){
        if(treesub[i] == comnums && edge[1].len - fadis[i] <= va){  //i号点向上的边是comnums条链的一条公共边 
            return true;    //如果最长链去掉这条边可以使得链长不超过va(其他链去掉该边就更短了),可以满足 
        }   
    }
    return false;           //如果没有公共边,或者公共边不能让最长链长减少至不超过va,则不能满足 
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i < n; i++){
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        a[x].push_back(make_pair(y, t));
        a[y].push_back(make_pair(x, t));
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        int cofa = lca(x, y);
        edge[i] = (Info){x, y, cofa, d[x] + d[y] - 2*d[cofa] + 1, b[x] + b[y] - 2*b[cofa]};
    }

    sort(edge+1, edge+m+1, Mycomp); //按照链长度降序 

    int L = -1, R = edge[1].len;    //-1是肯定不行的,最优情况是0,(L, R]的情况二分 
    while(L + 1 < R){
        int mid = (L + R) >> 1;
        if(check(mid)) R = mid; else L = mid;
    }

    printf("%d\n", R);
    return 0;
}

//一开始就把dfs序列(先子后己)拿出来放入数组,求前缀和的时候遍历数组就很快了(比递归求快多了) 
#include<bits/stdc++.h>
#define fi first
#define se second
#define si size()
#define UI unsigned int
using namespace std;
const int N = 3e5+10, M = 20;    
vector<pair<int, int> > a[N];   //原始边 
int b[N], d[N], fadis[N], f[N][M];  //距根长度, 深度, 与父结点距离, 倍增数组 
int dfsord[N], dfst = 0;        //dfs序列(先子后己) 
struct Info{
    int x, y, cofa, nodes, len; //最近公共祖先,两点之间的点数、长度 
}edge[N];                   //原始链起点终点及求得数据 
int treesub[N];
int n, m;
void dfs(int x, int fa){
    for(UI i = 0; i < a[x].si; i++){
        int y = a[x][i].fi, z = a[x][i].se;
        if(y == fa) continue;
        b[y] = b[x] + z, d[y] = d[x] + 1;   //距根长度、深度(根的深度为0) 
        fadis[y] = z;       //父结点距离 
        f[y][0] = x;
        for(int j = 1; j < M; j++){
            f[y][j] = f[f[y][j-1]][j-1];
        }               //更新倍增数组,为求lca准备 
        dfs(y, x);
    }
    dfsord[++dfst] = x;     //dfs序列(先子后己)  
}
int lca(int x, int y){
    if(d[x] < d[y]) swap(x, y);
    for(int i = M-1; i >= 0; i--){
        if(d[f[x][i]] >= d[y]) x = f[x][i];
    }
    if(x == y) return x;
    for(int i = M-1; i >= 0; i--){
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}
bool Mycomp(const Info&a, const Info&b){
    return a.len > b.len;
}
bool check(int va){     //如果答案是va,看是否能够满足,需要将链长超过va的链的公共边找出来
    memset(treesub, 0, sizeof(treesub));
    int comnums = 0;                    //有comnums条链长超过va,树上差分(边权) 
    for(int i = 1; i <= m && edge[i].len > va; i++){
        comnums = i;
        int x = edge[i].x, y = edge[i].y, z = edge[i].cofa;
        treesub[x]++, treesub[y]++, treesub[z] -= 2;//树上差分(边权),记录该边被经过的次数 
    }

    //求前缀和  
    for(int i = 1; i < n; i++){ //dfs序最后一个点是1,不需要贡献给父结点 
        int y = dfsord[i], x = f[y][0]; //dfs第i号点y, 其父结点x 
        treesub[x] += treesub[y];   //y的子树前缀和累计至父结点x上
    }                           //树上差分(边权)的前缀和,表示该边被若干条链经过 
    for(int i = 1; i <= n; i++){
        if(treesub[i] == comnums && edge[1].len - fadis[i] <= va){  //i号点向上的边是comnums条链的一条公共边 
            return true;    //如果最长链去掉这条边可以使得链长不超过va(其他链去掉该边就更短了),可以满足 
        }
    }
    return false;           //如果没有公共边,或者公共边不能让最长链长减少至不超过va,则不能满足 
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i < n; i++){
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        a[x].push_back(make_pair(y, t));
        a[y].push_back(make_pair(x, t));
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        int cofa = lca(x, y);
        edge[i] = (Info){x, y, cofa, d[x] + d[y] - 2*d[cofa] + 1, b[x] + b[y] - 2*b[cofa]};
    }

    sort(edge+1, edge+m+1, Mycomp); //按照链长度降序 

    int L = -1, R = edge[1].len;    //-1是肯定不行的,最优情况是0,(L, R]的情况二分 
    while(L + 1 < R){
        int mid = (L + R) >> 1;
        if(check(mid)) R = mid; else L = mid;
    }

    printf("%d\n", R);
    return 0;
}

算法3

(巧妙处理) $O(nlogn)$

将全部链根据长度降序
将最长链起点到终点重新编号,然后以起点为根遍历全部点,
若为最长链结点的子树,则该子树的全部结点编号为该结点相同编号,
则其他链的起点和终点的编号就和最长链经过的点形成的公共点同号。
比如:最长链经过1 2 3 4 ……n
某条其他链的起点是2的子树,则该起点编号就是2
终点是4的子树,则该终点编号就是4
该链与最长链的公共部分就是[2,4]
最终答案可能是最长链去掉最长边之后的值v1(该值不小于次长链的值v2)
如果去掉最长边之后的值v1小于v2,则答案可能是v2,
所以不能轻易说去掉那条边的值,应该是经过全部验证:
1、去掉最长链的最长边之后的值,与 v2 比较的较大值
2、去掉最长链和次长链的公共边的最大边之后的值,与次次长v3比较的较大值
3、去掉最长、次长、次次长的公共边的最大值,与v4比较。。。
。。。
如果某轮下来没有公共边了,则结束

C++ 代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define si size()
#define UI unsigned int
using namespace std;
const int N = 3e5+10, M = 20;    
vector<pair<int, int> > a[N];   //原始边 
int b[N], d[N], f[N][M];    //距根长度, 深度, 倍增数组 
struct Info{
    int x, y, cofa, nodes, len; //最近公共祖先,两点之间的点数、长度 
}edge[N];                   //原始链起点终点及求得数据 
int nord[N], nval[N];       //每个点的新编号,最长链的每条边的长度 
int st[N][M];               //最长链的每条边长形成ST表为求RMQ 
int n, m;
void dfs(int x, int fa){
    for(UI i = 0; i < a[x].si; i++){
        int y = a[x][i].fi, z = a[x][i].se;
        if(y == fa) continue;
        b[y] = b[x] + z, d[y] = d[x] + 1;   //距根长度、深度(根的深度为0) 
        f[y][0] = x;
        for(int j = 1; j < M; j++){
            f[y][j] = f[f[y][j-1]][j-1];
        }               //更新倍增数组,为求lca准备 
        dfs(y, x);
    }
}
int lca(int x, int y){
    if(d[x] < d[y]) swap(x, y);
    for(int i = M-1; i >= 0; i--){
        if(d[f[x][i]] >= d[y]) x = f[x][i];
    }
    if(x == y) return x;
    for(int i = M-1; i >= 0; i--){
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}
bool Mycomp(const Info&a, const Info&b){
    return a.len > b.len;
}
void GetNordOfLink(){   //给最长边经过的点进行编号(1..) 
    int x = edge[1].x;
    for(int i = 1; i <= d[edge[1].x] - d[edge[1].cofa] + 1; i++){
        nord[x] = i;
        x = f[x][0];
    }                   //[x, lca]编号 
    int y = edge[1].y;  
    for(int i = edge[1].nodes; i > edge[1].nodes - (d[edge[1].y] - d[edge[1].cofa]); i--){
        nord[y] = i;
        y = f[y][0];    //(lca, y]编号 
    }   
}
void dfsn(int x, int fa){
    for(UI i = 0; i < a[x].si; i++){
        int y = a[x][i].fi, z = a[x][i].se;
        if(y == fa) continue;
        if(!nord[y]) nord[y] = nord[x]; //形成新的编号 
        else nval[++nval[0]] = z;       //是最长链的边,边数是点数少1,即edge[1].nodes-1,即nval[0]
        dfsn(y, x);
    }   
}
void CreateST(int n){               //最长链的每条边长形成ST表为求RMQ 
    for(int i = 1; i <= n; i++) st[i][0] = nval[i];
    int t = log(n) / log(2) + 1;
    for(int j = 1; j < t; j++){
        for(int  i = 1; i <= n - (1<<j) + 1; i++){
            st[i][j] = max(st[i][j-1], st[i + (1<<(j-1))][j-1]);
        }
    }
}
int ST_query(int l, int r){         //查询边长的最大值 
    int k = log(r - l + 1) / log(2);
    return max(st[l][k], st[r - (1<<k) + 1][k]);
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i < n; i++){
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        a[x].push_back(make_pair(y, t));
        a[y].push_back(make_pair(x, t));
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        int cofa = lca(x, y);
        edge[i] = (Info){x, y, cofa, d[x] + d[y] - 2*d[cofa] + 1, b[x] + b[y] - 2*b[cofa]};
    }

    sort(edge+1, edge+m+1, Mycomp); //按照链长度降序 
    GetNordOfLink();        //给最长边经过的点进行编号(1..) 
    dfsn(edge[1].x, 0);     //重新遍历整棵树形成每个点的新编号
                            //对于不是最长链上的点x,若挂在新编号i号结点上,则整个子树结点编号都设为i 
    CreateST(nval[0]);      //对最长链的按顺序产生的边长做ST表为求RMQ 

    int ans = edge[1].len;  //默认是最长链的长度 
    int L = 1, R = nval[0]+1;
    for(int i = 1; i <= m ;i++){
        int ll = nord[edge[i].x], rr = nord[edge[i].y];
        if(ll > rr) swap(ll, rr);       //取得第i长链的起点和终点,形成区间[ll, rr]
        L = max(L, ll), R = min(R, rr); //更新[L, R]
        if(R <= L) break;               //如果公共边不存在,则结束
        ans = min(ans, max(edge[1].len - ST_query(L, R-1), edge[i+1].len));
                //找出公共边中最长的一条长度设为0,则第1~i条链都减少相同的值
                //只要让最长链长减掉该值,和,第i+1条链长比较,取较大值刷新ans即可
    }

    printf("%d\n", ans);
    return 0;
}
/*
输入样例:
6 3 
1 2 3 
1 6 4 
3 1 7 
4 3 6 
3 5 5 
3 6 
2 5 
4 5
输出样例:
11
*/


活动打卡代码 AcWing 350. 巡逻

氘爸-wt
2个月前
/*
n个村庄,从1号点开始遍历回到1号点,就是一次dfs,每条边被走了2次, 
    在没加边的情况下,路程应该是(n - 1) * 2
在一棵树上加一条边(要求增加的边必须走过一次),必然存在环,
    遍历时,可以使得环上的边只走一次(自行画图可得),
    必然:环越长越好,取直径两端加边最佳。
        若直径长度为L1,因为环上的边只需要走过一次,所以答案可以减去L1,
        新增边必须走一次,再加上1,此时答案为(n - 1) * 2 - L1 + 1
若再加一条边,也需要再找次长链的两端架桥梁 
    必然:除了之前的直径,再找另一条“稍短的最长链”
    两种情况:
        1、此“稍短的最长链”L2和第一次的直径没有公共边,则同理得
            此时答案为(n - 1) * 2 - L1 + 1 - L2 + 1
        2、若存在公共边,公共边长度设为b,此“稍短的最长链”剩余长度为a
            即总长为a + b;但是公共边必须走来回才能回到起点(自行画图可得) 
                如果在两端架桥梁,实际节省a + b - 2 * b = a - b
                即节省的长度为a - b,该值可正可负,
                若为负,则使得总路程还增加了,所以不见得最优
                也可以理解为该两端之间的距离为a - b
            自然想到(大神的智慧):将第一次求得直径上的边长改为-1
                在求“稍短的最长链”时,该两端距离就是a - b,参与比较即可 
            在实际最后求得的“稍短的最长链”时,就是最佳的,长度为L2
                同理得此时答案为(n - 1) * 2 - L1 + 1 - L2 + 1
    两种情况的答案是一致的。 
实现方法:
    1、先求直径L1,标记每个点向下的“最长值、点,次长链、点 ”
    2、按图索骥,将直径边的边长改为-1
    3、再求直径L2。
答案:(n - 1) * 2 - L1 + 1 - L2 + 1 
*/ 
#include<bits/stdc++.h>
#define UI unsigned int
#define PP pair<int, int>
using namespace std;
const int N = 1e5+10;
vector<PP> a[N];                    //邻接表,邻接点、边长 
int d1[N], s1[N], d2[N], s2[N];     //最长值、点,次长值、点 
int K, n, L;                        //L为直径长度 
bool FLG;                           //是否找到直径点
void dfs(int x, int fa){            //寻找直径,记录每个点向下的d1,s1,d2,s2 
    for(UI i = 0; i < a[x].size(); i++){
        int y = a[x][i].first, z = a[x][i].second;
        if(y == fa) continue;
        dfs(y, x);
        if(d1[y] + z > d1[x]){              //超过最长链 
            d2[x] = d1[x]; s2[x] = s1[x];   //先更新次长
            d1[x] = d1[y] + z; s1[x] = i;   //更新最长(记录是第i个儿子,默认是-1)
        }else if(d1[y] + z > d2[x]){        //超过次长链
            d2[x] = d1[y] + z; s2[x] = i;   //更新次长(记录是第i个儿子,默认是-1)
        }
        L = max(L, d1[x] + d2[x]);          //最长链+次长链,更新L
    }
}
void findmaxgivefu1(int x, int fa, int len){//直径经过的边长设为-1
    if(FLG) return;                         //FLG为true说明已找到直径点 
    if(d1[x] + d2[x] == len){               //x是直径经过点 
        if(s1[x] != -1){                    //x向下的最长链存在 
            int dir = s1[x];                //第dir条边 
            int y = a[x][dir].first;
            a[x][dir].second = -1;          //x到y的边长变为-1 
            dir = s1[y];                    //y向下最长链的方向(若不存在则为-1)
            while(dir != -1){               //沿着最长链子树方向将边长都设为-1
                a[y][dir].second = -1;
                y = a[y][dir].first;
                dir = s1[y];
            }           
        }
        if(s2[x] != -1){                    //x向下的次长链存在 
            int dir = s2[x];                //第dir条边 
            int y = a[x][dir].first;
            a[x][dir].second = -1;          //x到y的边长变为-1 
            dir = s1[y];                    //y向下最长链的方向(若不存在则为-1)
            while(dir != -1){               //沿着最长链子树方向将边长都设为-1
                a[y][dir].second = -1;
                y = a[y][dir].first;
                dir = s1[y];
            }           
        }       
        FLG = true;                         //已找到直径点,标记FLG为true 
        return;
    }
    for(UI i = 0; i < a[x].size(); i++){    //遍历子树 
        int y = a[x][i].first;
        if(y == fa) continue;
        findmaxgivefu1(y, x, len);
    }
}
int main(){
    scanf("%d%d", &n, &K);
    for(int i = 1; i < n; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(make_pair(y, 1));    //邻接表 
        a[y].push_back(make_pair(x, 1));
    }

    int ans = (n - 1) * 2;                  //不加边的路径长度 
    memset(d1, 0, sizeof(d1));
    memset(s1, -1, sizeof(s1));
    memset(d2, 0, sizeof(d2));
    memset(s2, -1, sizeof(s2));
    L = 0;
    dfs(1, 0);
    ans -= L - 1;                           //直径长度扣掉,加上新边 

    if(K == 2){                             //还要增加一条新边 
        FLG = false;                        //还未找到直径点 
        findmaxgivefu1(1, 0, L);            //直径经过的边长设为-1 
        memset(d1, 0, sizeof(d1));
        memset(s1, -1, sizeof(s1));
        memset(d2, 0, sizeof(d2));
        memset(s2, -1, sizeof(s2));
        L = 0;
        dfs(1, 0);
        ans -= L - 1;                       //直径长度扣掉,加上新边 
    }

    printf("%d\n", ans);
    return 0;
}



活动打卡代码 AcWing 349. 黑暗城堡

氘爸-wt
2个月前
/*
最短路径生成树问题
1、dijkstra求出从1开始到每个点的最短距离,f[] 
2、按照最短距离值对序号进行排序,ford[]
3、按序号ford[j]逐一增加树结点(1号点不需要尝试),
    如果f[j] == f[x] + a[x][j],
        则说明可以从x方向延伸过来增加树边,
    根据可行方向数量,累乘至ans,(ans的初值为1,注意LL取模) 
*/
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N = 1001;
int a[N][N];    //邻接矩阵
int f[N];       //最短路
bool vis[N];    //dijkstra访问过的点 
int n, m;
int ford[N];    //对最短路径点排序 
void dijkstra(){
    memset(f, 0x3f, sizeof(f));
    f[1] = 0;                               //1点是起点,1-1路径长度为0 
    for(int i = 1; i <= n; i++){            
        int x = n+1, minL = INF;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && f[j] < minL){
                x = j, minL = f[j];
            }
        }
        vis[x] = true;                      //找到未访问点中的最小值点,访问 
        for(int j = 1; j <= n; j++){        //拓展 
            if(vis[j]) continue;            //j已经访问过 
            int y = j, z = a[x][j];         //拓展点、距离 
            if(f[x] + z < f[y]){            //更优 
                f[y] = f[x] + z;            //刷新最短路径长度 
            }
        }
    }
}
bool Mycomp(const int&a, const int&b){      //根据最短路径值对序号升序 
    return f[a] < f[b];
}
void calcans(){
    for(int i = 1; i <= n; i++){
        ford[i] = i;
    }
    sort(ford+1, ford+n+1, Mycomp);         //根据最短路径值对序号升序

    LL ans = 1;
    for(int i = 2; i <= n; i++){            //1号不要考虑 
        int x = ford[i], t = 0;
        for(int j = 1; j <= n; j++){        //x可以由j方向走过来 
            if(f[x] == f[j] + a[x][j]) t++; //统计可行方向数量 
        }
        ans = (ans * t) % 0x7fffffff;       //累乘取模 
    }

    printf("%lld\n", ans);
}
int main(){
    memset(a, 0x3f, sizeof(a));
    scanf("%d%d", &n, &m);
    while(m--){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = a[y][x] = z;
    }   //任意两点最短路、邻接矩阵存储初始图信息 

    dijkstra();
    calcans();
    return 0;
}
/*
7 11
1 2 2
1 3 3
1 4 1
2 3 1
2 5 1
3 5 1
3 6 1
4 6 1
4 7 2
5 6 1
6 7 1

12
*/ 


活动打卡代码 AcWing 348. 沙漠之王

氘爸-wt
2个月前
/*
prim算法不超时(完全图适合prim算法求最小生成树) 
需要取一些边,使得"总成本(累计高度差) /总长度"最小,
可以分数倒数看问题,即"总长度 / 总成本(累计高度差)"最大, 设为L 
属于0/1分数规划问题 
每条边长设为"长度 - L * 成本(高度差)",取最大值累计(最大生成树)
若非负,则L还可以取更大,否则L只能取更小
二分求解答案。 
*/ 
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1001;
struct Dot{
    int x, y, high;
} a[N];
int n;
double f[N];
bool vis[N];
int calcHsub(Dot a, Dot b){                         //计算高度差 
    return abs(a.high - b.high);
}
double calcDis(Dot a, Dot b){                       //计算两点之间的距离 
    int x = a.x - b.x;
    int y = a.y - b.y;
    return sqrt(x * x + y *y);
}
bool check(double L){
    double s = 0;
    fill(f+1, f+n+1, -INF); f[1] = 0;           //注意double不能memset-0x3f 
    memset(vis, 0, sizeof(vis));            //访问没 
    for(int k = 1; k <= n; k++){
        double maxdis = -INF;               //寻找未访问的最大f[i]值的点 
        int x;
        for(int i = 1; i <= n; i++){
            if(!vis[i] && f[i] > maxdis){
                maxdis = f[i], x = i;
            }
        }
        vis[x] = true;                      //访问 
        s += maxdis;                        //累计取得的最大值,即边长 
        for(int i = 1; i <= n; i++){        //拓展,刷新f[] 
            if(vis[i]) continue;
            int hsub = calcHsub(a[x], a[i]);    //高度差 
            double dis = calcDis(a[x], a[i]);   //两点之间的距离 
            double hdisLsub = dis - L * hsub;   //ai-L*bi值,即边长 
            f[i] = max(f[i], hdisLsub); 
        }
    }
    return s >= 0;                                  //非负则可取更大的L 
}
int main(){
    while(scanf("%d", &n) && n){
        for(int i = 1; i <= n; i++){
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            a[i] = (Dot){x, y, z};                  //点 
        }

        double l = 0, r = 10000000;                 //分数值区间 
        while(l + 1e-6 < r){                        //临界,实数不能相等 
            double mid = (l + r) / 2;
            if(check(mid)) l = mid; else r = mid;
        }       

        printf("%.3f\n", 1.0/l);    //答案要求:"总成本(累计高度差) /总长度"最小 
    }
    return 0;
}
/*
10
5 5 17
8 9 55
1 4 82
6 9 85
8 0 66
0 8 90
4 0 91
7 4 76
9 6 38
4 4 18
10
5 7 99
5 0 71
5 3 40
4 2 23
1 9 86
1 0 8
6 2 39
4 3 47
7 6 41
8 2 57
0

1.381
2.205
*/

/*
直接解决最小的问题,使得"总成本(累计高度差) /总长度"最小,设为L 
属于0/1分数规划问题的变通(0/1分数规划问题是讨论最大的问题)
每条边长设为"成本(高度差) - L * 长度",取最小值累计(最小生成树)
若非正,则L还可以取更小,否则L只能取更大
二分求解答案。 
*/ 
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1001;
struct Dot{
    int x, y, high;
} a[N];
int n;
double f[N];
bool vis[N];
int calcHsub(Dot a, Dot b){                         //计算高度差 
    return abs(a.high - b.high);
}
double calcDis(Dot a, Dot b){                       //计算两点之间的距离 
    int x = a.x - b.x;
    int y = a.y - b.y;
    return sqrt(x * x + y *y);
}
bool check(double L){
    double s = 0;
    fill(f, f+n+1, INF); f[1] = 0;          //注意double不能memset-0x3f 
    memset(vis, 0, sizeof(vis));            //访问没 
    for(int k = 1; k <= n; k++){
        double mindis = INF;                //寻找未访问的最小f[i]值的点 
        int x;
        for(int i = 1; i <= n; i++){
            if(!vis[i] && f[i] < mindis){
                mindis = f[i], x = i;
            }
        }
        vis[x] = true;                      //访问 
        s += mindis;                        //累计取得的最小值,即边长 
        for(int i = 1; i <= n; i++){        //拓展,刷新f[] 
            if(vis[i]) continue;
            int hsub = calcHsub(a[x], a[i]);    //高度差 
            double dis = calcDis(a[x], a[i]);   //两点之间的距离 
            double hsubLdis = hsub - L * dis;   //ai-L*bi值,即边长 
            f[i] = min(f[i], hsubLdis); 
        }
    }
    return s <= 0;                                  //非正则可取更小的L 
}
int main(){
    while(scanf("%d", &n) && n){
        for(int i = 1; i <= n; i++){
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            a[i] = (Dot){x, y, z};                  //点 
        }

        double l = 0, r = 10000000;                 //分数值区间 
        while(l + 1e-6 < r){                        //临界,实数不能相等 
            double mid = (l + r) / 2;
            if(check(mid)) r = mid; else l = mid;
        }       

        printf("%.3f\n", l);
    }
    return 0;
}

/*
Kruscal实现超时4个点
1000个点,完全图,1,000,000条边,每次排序20,000,000次比较
二分需要40次循环,总计800,000,000次运算,超时
只有1000个点,最小生成树最多只需要取999条边,适合使用prim算法 
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1001, NN = N*N;
struct Info{
    int l, r, hsub;
    double dis, hsubLdis;
}edge[NN];
struct Dot{
    int x, y, high;
}dot[N];
int n, tot, fa[N];
int calcHsub(Dot a, Dot b){                         //计算高度差 
    return abs(a.high - b.high);
}
double calcDis(Dot a, Dot b){                       //计算两点之间的距离 
    int x = a.x - b.x;
    int y = a.y - b.y;
    return sqrt(x * x + y *y);
}
bool Mycomp(const Info&a, const Info&b){            //边长升序 
    return a.hsubLdis < b.hsubLdis;
}
int findFa(int x){
    if(fa[x] == x) return x;
    return fa[x] = findFa(fa[x]);
}
bool check(double L){
    for(int i = 1; i <= tot; i++){                  //计算边长(高度差-L*距离)
        edge[i].hsubLdis = edge[i].hsub - L * edge[i].dis;
    }
    sort(edge + 1, edge + tot +1, Mycomp);          //升序 
    for(int i = 1; i <= n; i++){                    //并查集 
        fa[i] = i;
    }
    double s = 0;
    int t = n - 1;                                  //共需要使用n-1条边 
    for(int i = 1; i <= tot; i++){                  //Kruscal
        int ll = edge[i].l, rr = edge[i].r;         //两个点 
        int rootl = findFa(ll), rootr = findFa(rr); //两个根 
        if(rootl != rootr){                         //不同集,合并 
            fa[rootl] = rootr;
            s += edge[i].hsubLdis;                  //取得的边长累计 
            if(--t == 0) break;
        }
    }
    return s <= 0;                                  //非正则可取更小的L 
}
int main(){
    while(scanf("%d", &n) && n){
        for(int i = 1; i <= n; i++){
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            dot[i] = (Dot){x, y, z};                //点 
        }

        tot = 0;
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j <= n; j++){
                int hsub = calcHsub(dot[i], dot[j]);
                double dis = calcDis(dot[i], dot[j]);
                edge[++tot] = (Info){i, j, hsub, dis, 0};   //边(无向图) 
            }
        }

        double l = 0, r = 1000000;                  //分数值区间 
        while(l + 1e-6 < r){                        //临界,实数不能相等 
            double mid = (l + r) / 2;
            if(check(mid)) r = mid; else l = mid;
        }       

        printf("%.3f\n", l);
    }
    return 0;
}



活动打卡代码 AcWing 234. 放弃测试

氘爸-wt
2个月前
/*
0/1分数规划问题(n组a[i]、b[i]中,挑出n-k组使得 ∑a / ∑b 要最大) 
采用二分法求解
二分分数值L,
    如果对n-k组表达式求∑(a[i]-L*b[i]) ≥0,则L偏小,可尝试更大的L
    否则,只可尝试更小的L。
原理参考0x39 0/1分数规划 的解释。 
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1001;
int a[N], b[N], n, k;
double c[N];
bool check(double L){
    for(int i = 1; i <= n; i++){                    //计算出n组结果放入c[] 
        c[i] = a[i] - L * b[i];
    }
    sort(c + 1, c + n + 1);                         //升序 
    double s = 0;
    for(int i = k+1; i <= n; i++){                  //排除前k项,只取n-k项的大值 
        s += c[i];
    }
    return s >= 0;                                  //非负则可取更大的L 
}
int main(){
    while(scanf("%d%d", &n, &k) && (n || k)){
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        for(int i = 1; i <= n; i++){
            scanf("%d", &b[i]);
        }

        double l = 0, r = 1;                        //分数值区间 
        while(l + 1e-6 < r){                        //临界,实数不能相等 
            double mid = (l + r) / 2;
            if(check(mid)) l = mid; else r = mid;
        }

        int ans = round(l * 100);                   //百分制,且四舍五入取整 
        printf("%d\n", ans);
    }
    return 0;
}



活动打卡代码 AcWing 386. 社交网络

氘爸-wt
2个月前
/*
NOI2007题目,巧妙推导方法,其实就是利用dijkstra求最短路(虽然略烦,但比起floyd更好理解) 
邻接矩阵存储初始图信息,稍慢,不影响(复杂度本来就是n^3) 
题意:i、j之间求得最短路径条数,计算其中k作为中间点所占的比例,
        总计不同i、j的累计值(i≠j,i≠k,j≠k) 
    比如:有4个点1~4, 
        中间点为1,计算2到3的最短路径经过1的条数 / 2到3的最短路径条数
            +      计算2到4的最短路径经过1的条数 / 2到4的最短路径条数
            +      计算3到2的最短路径经过1的条数 / 3到2的最短路径条数
            +      计算3到4的最短路径经过1的条数 / 3到4的最短路径条数
            +      计算4到2的最短路径经过1的条数 / 4到2的最短路径条数
            +      计算4到3的最短路径经过1的条数 / 4到3的最短路径条数
        输出累计和,保留三位小数;
        中间点为2,计算...+...+... 输出累计和,保留三位小数
        中间点为3,计算...+...+... 输出累计和,保留三位小数
        中间点为4,计算...+...+... 输出累计和,保留三位小数
分析:
1、总点数n不超过100,可以支持O(n^3)
2、以k为起点做dijkstra,求单源最短路径,顺便求解从k出发到任意点的最短路径长度f和条数g
3、统计时,以k作为中间点,k、i、j互不相等 
    如果f[i][j] == f[i][k] + f[k][j],说明i和j之间进过k可以形成最短路,
    //利用乘法原理,g[i][k] * g[k][j]就是经过k的最短路径条数
    //而且此刻,i到k,k到j,除了k是公共点,没有其他公共点
    //若存在公共点l,则i-l-k-l-j,此时i-l-j的距离更短,故假设不成立,而命题成立
    //所以乘法原理可用 
*/
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N = 101;
int a[N][N];    //邻接矩阵
int f[N][N];    //最短路
LL g[N][N];     //i到j之间最短路的条数 
bool vis[N];    //dijkstra访问过的点 
int n, m;
void dijkstra(){
    for(int k = 1; k <= n; k++){
            //从每个点出发做n次dijkstra
        f[k][k] = 0;                            //k点是起点,k-k路径长度为0 
        g[k][k] = 1;                            //路径条数1 
        memset(vis, 0, sizeof(vis));            //dijkstra访问点 
        for(int i = 1; i <= n; i++){            
            int x = n+1, minL = INF;
            for(int j = 1; j <= n; j++){
                if(!vis[j] && f[k][j] < minL){
                    x = j, minL = f[k][j];
                }
            }
            vis[x] = true;                      //找到未访问点中的最小值点,访问 
            for(int j = 1; j <= n; j++){        //拓展 
                if(!a[x][j]) continue;          //x 和 j 不直接关联
                int y = j, z = a[x][j];         //拓展点、距离 
                if(f[k][x] + z < f[k][y]){      //更优 
                    f[k][y] = f[k][x] + z;      //刷新最短路径长度 
                    g[k][y] = g[k][x];          //路径条数重新赋值 
                }else if(f[k][x] + z == f[k][y]){   //长度相等,说明来自不同方向的最短路径 
                    g[k][y] += g[k][x];         //累计路径条数 
                }
            }
        }
    }
}
void calcans(){
    for(int k = 1; k <= n; k++){
        double ans = 0;                             //比例累计初值为0 
        for(int i = 1; i <= n; i++){
            if(k == i) continue;
            for(int j = 1; j <= n; j++){
                if(k == j || i == j) continue;      //保证i、j、k互不相等 
                if(f[i][j] == f[i][k] + f[k][j]){   
                    //f[i][j] 与 经过k的两段之和 相等,说明经过k也可以是最短路径
                    //利用乘法原理,g[i][k] * g[k][j]就是经过k的最短路径条数
                    //而且此刻,i到k,k到j,除了k是公共点,没有其他公共点
                    //若存在公共点l,则i-l-k-l-j,此时i-l-j的距离更短,故假设不成立,而命题成立
                    //所以乘法原理可用 
                    ans += g[i][k] * g[k][j] * 1.0 / g[i][j];
                        //计算比例累计,乘法不会越界,因为g[i][k] * g[k][j] <= g[i][j]
                }
            }
        }
        printf("%.3lf\n", ans);
    }
}
int main(){
    memset(f, 0x3f, sizeof(f));
    scanf("%d%d", &n, &m);
    while(m--){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        f[x][y] = f[y][x] = a[x][y] = a[y][x] = z;
    }   //任意两点最短路、邻接矩阵存储初始图信息 

    dijkstra();
    calcans();
    return 0;
}
/*
5 6
1 2 1
1 4 1
1 5 1
2 3 1
3 4 1
4 5 1

3.000
1.000
1.000
3.000
0.000

5 6
1 2 2
1 4 1
2 3 2
2 4 1
3 4 3
4 5 2

0.000
3.333
0.000
8.333
0.000
*/

/*
使用floyd处理使编程更加简单
但理解更加困难一点 
*/ 
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 101;
int f[N][N];    //最短路
LL g[N][N];     //i到j之间最短路的条数,最多10^10,需要long long 
int n, m;
void floyd(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){            
            for(int j = 1; j <= n; j++){
                if(f[i][k] + f[k][j] < f[i][j]){    //如果更短 
                    f[i][j] = f[i][k] + f[k][j];    //更新最短 
                    g[i][j] = g[i][k] * g[k][j];    //乘法原理值重新赋值 
                }else if(f[i][k] + f[k][j] == f[i][j]){ //如果相等 
                    g[i][j] += g[i][k] * g[k][j];   //乘法原理值累计,即经过k也可以是最短路径 
                }
            }
        }
    }
}
void calcans(){
    for(int k = 1; k <= n; k++){
        double ans = 0;                             //比例累计初值为0 
        for(int i = 1; i <= n; i++){
            if(k == i) continue;
            for(int j = 1; j <= n; j++){
                if(k == j || i == j) continue;      //保证i、j、k互不相等 
                if(f[i][j] == f[i][k] + f[k][j]){   
                    //f[i][j] 与 经过k的两段之和 相等,说明g[i][j]包含了g[i][k] * g[k][j]
                    ans += g[i][k] * g[k][j] * 1.0 / g[i][j];
                        //计算比例累计,乘法不会越界,因为g[i][k] * g[k][j] <= g[i][j]
                }
            }
        }
        printf("%.3lf\n", ans);
    }
}
int main(){
    memset(f, 0x3f, sizeof(f));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) f[i][i] = 0;    //自环距离0,即无自环 
    while(m--){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        f[x][y] = f[y][x] = z;  //邻接矩阵存储初始图信息
        g[x][y] = g[y][x] = 1;  //两点之间的当前长度的路径条数,初始就是直连的1条 
    }   

    floyd();    
    calcans();
    return 0;
}



氘爸-wt
2个月前
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 110;
int a[N][N];
int main(){
    memset(a, 0x3f, sizeof(a));
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--){
        int x, y;
        scanf("%d%d", &x, &y);
        a[x][y] = a[y][x] = 1;
    }

    int ans = 0;
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i][j] < INF) ans = max(ans, a[i][j]);
        }
    }

    printf("%d\n", ans);
    return 0;
}



活动打卡代码 AcWing 383. 观光

氘爸-wt
2个月前
/*
简化方法
最短路径长度和条数通过dijkstra逐步递推求得
    用“前导点最短路径值 + 边长” 刷新 “当前点最短路径值 ”
次短(最短+1)路径条数可通过两个方向得到
    前导点最短路径值 + 边长 ==  当前点次短路径值
    前导点次短路径值 + 边长 ==  当前点次短路径值
    累计次短路径条数
实现过程中,有陷阱:
    当前已经是最短路径值,可以刷新下一拓展点的最短路径值、条数、次短路径条数
    但还不能马上使用当前次短路径条数 去 更新 下一拓展点的次短路径的条数
    因为当前点的次短路径条数可能还未刷新到位(可能还会由其他点延伸过来刷新) 
方法: 
    寻找未访问过的,最短路径值和次短路径值点,的最小值,开始拓展
    如果是最短路径值点最优,开始拓展
        可以刷新目标点的最短路径值和条数、次短路径条数
        具体看程序部分(比最短短1、短很多、相等、大1) 
    如果是次短路径值点最优,开始拓展
        只是增加目标点的次短路径条数
        具体看程序部分(和次短相等)
注意:次短不可能刷新最短,否则就可以拿最短刷新最短了,^-^ 
*/ 
#include<bits/stdc++.h>
#define UI unsigned int
#define INF 0x3f3f3f3f
#define PP pair<int,int>
using namespace std;
const int N = 1010;
struct Info{
    int minL, mN, sN;                   //最短路径长度、最短条数、次短条数 
    bool vism, viss;                    //dijkstra时有没有访问过(最短、次短)
    void refresh(int x, int y, int z){         //更新minL、mN、sN 
        minL = x, mN = y, sN = z;
    }
} f[N];
int sortf[N];                           //逐步访问点的序列(最短路径长度值是非下降序列) 
vector<PP> a[N];                        //邻接表 
int n, m;
void dijkstra(int be, int en){
    for(int i = 1; i <= n; i++){
        f[i] = (Info){INF, 0, 0, 0, 0};
    }       //每个点初始化(最短路径最大化、最短条数0、次短条数0,未访问过(最短、次短))
    f[be] = (Info){0, 1, 0, 0, 0};     //起点(最短路径0、最短条数1、次短条数0,未访问过(最短、次短))
    for(int i = 1; i <= n+n; i++){        //dijkstra 
        int x = n+1, minV = INF, ms = 0;
        for(int j = 1; j <= n; j++){
            if(f[j].vism == false && f[j].minL < minV){
                minV = f[j].minL, x = j, ms = 0;                    //最短路 
            }else if(f[j].viss == false && f[j].sN && f[j].minL+1 < minV){
                minV = f[j].minL+1, x = j, ms = 1;                  //次短路 
            }
        }
        if(x == n+1) break;

        if(ms == 0){                                        //最短路点触发(更新) 
            f[x].vism = true;                               //访问过了 
            for(UI j = 0; j < a[x].size(); j++){            //刷新拓展点的最短路径值和条数 
                int y = a[x][j].first, z = a[x][j].second;  //目标点、边长 
                if(f[x].minL + z < f[y].minL){              //更小 
                    if(f[x].minL + z == f[y].minL - 1){     //恰好小1 
                        f[y].refresh(f[x].minL + z, f[x].mN, f[y].mN);  
                            //更新最短路,原最短路条数变成次短路条数 
                    }else{                                  //小得更多 
                        f[y].refresh(f[x].minL + z, f[x].mN, 0);
                            //更新最短路,原次短路条数清零 
                    }                   
                }else if(f[x].minL + z == f[y].minL){       //相等,则增加最短路条数 
                    f[y].refresh(f[y].minL, f[y].mN + f[x].mN, f[y].sN);
                }else if(f[x].minL + z == f[y].minL + 1){   //大1,则增加次短路条数 
                    f[y].refresh(f[y].minL, f[y].mN, f[y].sN + f[x].mN);
                }
            }
        }else{
            f[x].viss = true;                               //访问过了 
            for(UI j = 0; j < a[x].size(); j++){            //刷新拓展点的次短路条数 
                int y = a[x][j].first, z = a[x][j].second;  //目标点、边长
                if(f[x].minL + z == f[y].minL){             //最短路相等(就是次短路相等) 
                    f[y].refresh(f[y].minL, f[y].mN, f[y].sN + f[x].sN);
                }                                           //增加次短路条数 
            }
        }
    }
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        for(int i = 1; i <= n; i++){            //邻接表初始化 
            a[i].clear();
        }

        scanf("%d%d", &n, &m);
        while(m--){
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            a[x].push_back(make_pair(y, z));    //邻接表 
        }
        int be, en;
        scanf("%d%d", &be, &en);                //begin和end 

        dijkstra(be, en);                       //求每个点的最短条数+次短条数 

        printf("%d\n", f[en].mN + f[en].sN);    //终点的最短条数+次短条数 
    }
    return 0;
}
/*
1
4 8
1 2 2
1 2 3
1 3 2
2 3 1
2 4 2
3 2 1
3 4 2
3 4 3
1 4

6
*/

/*
复杂一点的方法
求:最短路的条数+最短路径长度大1的路径条数(次长路径) 
2≤N≤1000 ,直接O(n^2)的dijkstra即可,不需要堆优化 
分三步走 
一、dijkstra求最短路径的条数
    记录到当前点最短距离和路径条数
    初始点最短距离是0,条数是1
    碰到拓展点,刷新最短距离时,
        若小于原值,则更新最短距离,对到当前点的条数重新赋值(之前距离太大,已经作废)
        若等于原值,则累计到当前点的条数(多条路径来到当前位置) 
二、在dijkstra时访问到的点依次加入队列(到这些点的最短距离是非下降序列)
    按照最短距离值相等的一系列点做两遍拓展操作
        1、如果拓展边长度为1,指向点就在这一系列点中,则更新次长路径条数
            这一操作非常重要,等值点也可能加1互相到达,需要更新对方次长路径条数 
            不能直接更新后续点的次长路径 
        2、如果指向点不是这一系列点,
            当前点最短路径长度加上边长正好比指向点最短路径值大1,则更新 
            当前点最短路径长度+1,加上边长正好比指向点最短路径值大1,则更新
三、终点处最短路径条数+次长路径条数就是答案 
*/ 
#include<bits/stdc++.h>
#define UI unsigned int
#define INF 0x3f3f3f3f
#define PP pair<int,int>
using namespace std;
const int N = 1010;
struct Info{
    int minL, mN, sN;                   //最短路径长度、最短条数、次短条数 
    bool vis;                           //dijkstra时有没有访问过 
    void refresh(int x, int y){         //更新minL和mN 
        minL = x, mN = y;
    }
} f[N];
int sortf[N];                           //逐步访问点的序列(最短路径长度值是非下降序列) 
vector<PP> a[N];                        //邻接表 
int n, m;
void dijkstra(int be, int en){
    for(int i = 1; i <= n; i++){
        f[i] = (Info){INF, 0, 0, false};
    }   //每个点初始化(最短路径最大化、最短条数0、次短条数0,未访问过)
    f[be] = (Info){0, 1, 0, false};     //起点(最短路径0、最短条数1、次短条数0,未访问过) 
    for(int i = 1; i <= n; i++){        //dijkstra 
        int x = n+1, minV = INF;
        for(int j = 1; j <= n; j++){
            if(f[j].vis == false && f[j].minL < minV){
                minV = f[j].minL; x = j;
            }
        }
        if(x == n+1) break;             //未找到需访问点(本题图是连通的,暂无用) 
        sortf[i] = x;                   //逐个记录访问点 
        f[x].vis = true;                //访问过了 
        for(UI j = 0; j < a[x].size(); j++){            //刷新拓展点的最短路径值和条数 
            int y = a[x][j].first, z = a[x][j].second;  //目标点、边长 
            if(f[x].minL + z < f[y].minL){              //更小 
                f[y].refresh(f[x].minL + z, f[x].mN);
            }else if(f[x].minL + z == f[y].minL){       //相等 
                f[y].refresh(f[x].minL + z, f[y].mN+ f[x].mN);
            }
        }
    }

    vector<int> v(1, -1);           //记录等值的最后一个位置(-1之后的等值区间起点-1+1=0) 
    for(int i = 1; i < n; i++){
        int x = sortf[i], x1 = sortf[i+1];
        if(f[x].minL != f[x1].minL) v.push_back(i); //如果相邻不等值,则记录前一个(区间尾位置)
    }
    v.push_back(n);                 //第n个访问点是最后一个区间的尾位置 

    for(UI i = 0; i < v.size()-1; i++){
        int ll = v[i]+1, rr = v[i+1];       //区间起点和终点 
        for(int j = ll; j <= rr; j++){      //刷新等值点之间的次长路径条数 
            int x = sortf[j];
            for(UI k = 0; k < a[x].size(); k++){
                int y = a[x][k].first, z = a[x][k].second;
                if(z == 1 && f[x].minL == f[y].minL){   //等值点长度值+1就是目标点的次长路径长度 
                    f[y].sN += f[x].mN;
                }
            }
        }
        for(int j = ll; j <= rr; j++){      //刷新不等值点的次长路径条数 
            int x = sortf[j];
            for(UI k = 0; k < a[x].size(); k++){
                int y = a[x][k].first, z = a[x][k].second;
                if(f[x].minL == f[y].minL) continue;    //若等值点则跳过 
                if(f[x].minL + z == f[y].minL + 1){     //由最短路径长度值拓展 
                    f[y].sN += f[x].mN;
                }
                if(f[x].minL + 1 + z == f[y].minL + 1){ //由次短路径长度值拓展 
                    f[y].sN += f[x].sN;                 
                }
            }
        }       
    }
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        for(int i = 1; i <= n; i++){            //邻接表初始化 
            a[i].clear();
        }

        scanf("%d%d", &n, &m);
        while(m--){
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            a[x].push_back(make_pair(y, z));    //邻接表 
        }
        int be, en;
        scanf("%d%d", &be, &en);                //begin和end 

        dijkstra(be, en);                       //求每个点的最短条数+次短条数 

        printf("%d\n", f[en].mN + f[en].sN);    //终点的最短条数+次短条数 
    }
    return 0;
}
/*
1
4 8
1 2 2
1 2 3
1 3 2
2 3 1
2 4 2
3 2 1
3 4 2
3 4 3
1 4

6
*/


活动打卡代码 AcWing 345. 牛站

氘爸-wt
2个月前
//利用类矩阵乘法+快速幂,实现正好n条边从s到e的最短路径值 
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 110;
struct Info{
    int c[N][N];
}a, b;
map<int, int>mm;
int n, t, s, e, tot;
Info Mul(Info a, Info b){   //类矩阵乘法(乘积和),现为和的较小值 
    Info r;
    for(int i = 1; i <= tot; i++){
        for(int j = 1; j <= tot; j++){
            r.c[i][j] = INF;
            for(int k = 1; k <= tot; k++){
                r.c[i][j] = min(r.c[i][j], a.c[i][k] + b.c[k][j]);
            }
        }
    }
    return r;
}
//void pri(Info a){ //调试输出 
//  for(int i = 1; i <= tot; i++){
//      for(int j = 1; j <= tot; j++){
//          printf("%3d", a.c[i][j]);
//      }
//      puts("");
//  }
//  puts("");
//}
int main(){
    memset(a.c, 0x3f, sizeof(a.c));
    scanf("%d %d %d %d", &n, &t, &s, &e);
    while(t--){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        y = mm[y] ? mm[y] : mm[y] = ++tot;  //离散化 
        z = mm[z] ? mm[z] : mm[z] = ++tot;
        a.c[z][y] = a.c[y][z] = min(a.c[y][z], x);  //可能有重边 
    }

//  puts("a");pri(a);   //调试输出 
    b = a;              //经过一条边到达的最短路径 
    --n;                //再经过n-1条边,快速幂求解
    while(n){ 
        if(n & 1) b = Mul(b, a);
//          puts("b");pri(b);   //调试输出  
        a = Mul(a, a);
//      puts("a");pri(a);   //调试输出 
        n >>= 1;
    }

//  puts("b");pri(b);   //调试输出 
    printf("%d\n", b.c[mm[s]][mm[e]]);
    return 0;
}



活动打卡代码 AcWing 514. 寻找道路

氘爸-wt
2个月前
/*
题意:最短路径上每个点的出边指向的点必须能走到终点
方法:SPFA,单源最短路问题(SSSP)
首先,从终点t开始利用反向边图进行dfs1,标出可以经过的点h1[]
其次,从起点s开始利用正向边图进行dfs2(满足h1[]为true),
    对于碰到的点y的全部出边点,若都满足h1[]为true,则标出h2[]
最后,通过spfa对h2[]为true的点求从s到t的最短路径即可 
*/

#include<bits/stdc++.h>
#define UI unsigned int
using namespace std;
const int N = 10010, M = 200010, INF = 0x3f3f3f3f;
vector<int> a[N], b[N];
queue<int> q;
bool h1[N], h2[N], spfah[N];
int f[N];
void dfs1(int x){   //反向标出h1[] 
    if(h1[x]) return;   //已经标注过,说明存在环,返回 
    h1[x] = true;
    for(UI i = 0; i < b[x].size(); i++){
        dfs1(b[x][i]);
    }
}
void dfs2(int x){   //正向标出h2[] 
    if(h2[x]) return;   //已经标注过,说明存在环,返回
    h2[x] = true;
    for(UI i = 0; i < a[x].size(); i++){
        int y = a[x][i];
        if(!h1[y]) continue;    //不满足h1[y] 
        bool flg = true;
        for(UI j = 0; j < a[y].size(); j++){
            if(!h1[a[y][j]]){
                flg = false;
                break;
            }
        }           //只有出边全部h1[]才行 
        if(flg) dfs2(a[x][i]);
    }   
}
void spfa(int s, int t){
    if(!h2[s]) return;  //起点必须有效 
    f[s] = 0;
    spfah[s] = true;
    q.push(s);
    while(q.size()){
        int x = q.front(); q.pop();
        for(UI i = 0; i < a[x].size(); i++){
            int y = a[x][i];
            if(!h2[y]) continue;
            if(f[x] + 1 < f[y]){    //更优 
                f[y] = f[x] + 1;
                if(spfah[y]) continue;
                q.push(y);
            }
        }
    }
}
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    while(m--){
        int x, y;
        scanf("%d %d", &x, &y);
        a[x].push_back(y);      //正向边 
        b[y].push_back(x);      //反向边 
    }
    int s, t;
    scanf("%d %d", &s, &t);

    dfs1(t);
    dfs2(s);

    memset(f, 0x3f, sizeof(f));
    spfa(s, t);

    if(f[t] == INF) f[t] = -1;  //不成立 
    printf("%d\n", f[t]);
    return 0;
}