图论小结

Last_Reincarnation · 2019-10-15 18:52:34 · 个人记录

\mathfrak{\color{red}\boxed{\color{purple}\colorbox{red}{愿：如夏花般绚烂，如繁星般璀璨}}}

最短路

P1576 最小花费

在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人
之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。
    输入格式:
    第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。
    以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的
    手续费 (z<100)。
    最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。
    输出格式:
    共N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，
    你只需要输出 ans mod 100003后的结果即可。如果无法到达顶点i则输出0。

根据题意建双向边，倒着跑一边最短路（重点的dis为100），利率为(1-z/(100.0)，ok

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define Re register
using namespace std;

const double inf = (double)0x3f3f3f3f;
const int maxn = 100010;

int n, m;
int x, y, z, cnt, s, t;

int head[2010];
double dis[2010];
bool vis[2010];

struct Edge{
    int u, v, next;
    double w;
}e[maxn*2];

int f_;
char ch_;
template <class T>
    T read(T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        while (ch_ < '0' || ch_ > '9'){if (ch_ == '-') f_ = -1; ch_ = getchar();}
        while (ch_ >= '0' && ch_ <= '9') x_ = (x_ << 3) + (x_ << 1) + ch_ - 48, ch_ = getchar();
        return x_ *= f_;
    }

void add (int u, int v, double w){
    e[++cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
    return ;
}

void Spfa(){
    queue<int>Q;
    for (Re int i = 1;i <= n; ++i) dis[i] = inf;
    Q.push(t);
    vis[t] = 1;
    dis[t] = 100;
    while (!Q.empty()){
        x = Q.front();
        Q.pop();
        vis[x] = 0;
        for (Re int i = head[x]; i ;i = e[i].next){
//          cout<<dis[x]*100.0<<' '<<e[i].w*100.0<<'\n';
            if (dis[e[i].v] > (double)dis[x]/e[i].w){
                dis[e[i].v] = (double)dis[x]/e[i].w;
                if (vis[e[i].v]) continue;
                Q.push(e[i].v);
                vis[e[i].v] = 1;
            }
        }
    }
    return;
}

int main(){
    read(n);
    read(m);
    for (Re int i = 1;i <= m; ++i){
        read(x); read(y); read(z);
        add(x, y, (double)(1-z/(100.0)));
        add(y, x, (double)(1-z/(100.0)));
    }
    read(s);
    read(t);
    Spfa();
    printf("%.8lf", dis[s]);
    return 0;
}

P1342 请柬

在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。
他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或
她将留在那里一整天,邀请人们参与.
这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。
学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都
回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

输入格式：
第1行有两个整数n、m(1<=n,m<=1000000)，n是站点的个数，m是线路的个数。
然后有m行，每行描述一个线路，包括3个整数，起始点，目的地和价格。
总部在第1个站点，价钱都是整数，且小于1000000000。

输出格式：
输出一行，表示最小费用。

正反各跑一遍最短路即可

code

#include <iostream>
#include <cstdio>
#include <queue>
#define Re register
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1000100;

int n, m, cnt, cntf;
int u, v, w;
long long ans;
int head[maxn], headf[maxn], dis[maxn], disf[maxn];

bool vis[maxn], visf[maxn];

struct Edge{
    int u, v, w, next;
}e[maxn], ef[maxn];

struct note{
    int now, w;
    inline bool operator < (const note &a) const{
        return w > a.w;
    }
};

int f_;
char ch_;
template <class T>
    T read(T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        while (ch_ < '0' || ch_ > '9'){if (ch_ == '-') f_ = -1; ch_ = getchar();}
        while (ch_ >= '0' && ch_ <= '9') x_ = (x_ << 3) + (x_ << 1) + ch_ - 48, ch_ = getchar();
        return x_ *= f_;
    }

void add (int u, int v, int w){
    e[++cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
    return;
}

void addf (int u, int v, int w){
    ef[++cntf].u = u;
    ef[cntf].v = v;
    ef[cntf].w = w;
    ef[cntf].next = headf[u];
    headf[u] = cntf;
    return;
}

void dijkstra(){
    priority_queue<note>Q;
    for (Re int i = 1;i <= n; ++i) dis[i] = inf;
    Q.push((note){1, 0});
    dis[1] = 0;
    while (!Q.empty()){
        note top = Q.top();
        u = top.now;
        Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (Re int i = head[u]; i ;i = e[i].next){
            v = e[i].v;
            w = e[i].w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                Q.push((note){v, dis[v]});

            }
        }
    }
}

void dijkstraf(){
    priority_queue<note>Q;
    for (Re int i = 1;i <= n; ++i) disf[i] = inf;
    Q.push((note){1, 0});
    disf[1] = 0;
    while (!Q.empty()){
        u = Q.top().now;
        Q.pop();
        if (visf[u]) continue;
        visf[u] = 1;
        for (Re int i = headf[u]; i ;i = ef[i].next){
            v = ef[i].v;
            w = ef[i].w;
            if (disf[v] > disf[u] + w){
                disf[v] = disf[u] + w;
                Q.push((note){v, disf[v]});

            }
        }
    }
}

int main(){
    read(n);
    read(m);
    for (Re int i = 1;i <= m; ++i){
        read(u);
        read(v);
        read(w);
        add(u, v, w);
        addf(v, u, w);
    }
    dijkstra();
    dijkstraf();
    for (Re int i = 1;i <= n; ++i){
        ans += dis[i];
        ans += disf[i];
    }
    printf("%lld", ans);
    return 0;
}

P3084 [USACO13OPEN]照片Photo

农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。

于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了
编号a_i 到 b_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。

在拍完照片后，约翰发现了一个有趣的事情：每张照片中都有且仅有一只身上带有斑点的奶牛。约翰意识
到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛
群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

看完知道查分约束，不会写诶。。然后看题解，神TM一群dp dalao，只有个别dalao写了查分约束，然后学到了时间判负环QwQ

#include <iostream>
#include <cstdio>
#include <time.h>
using namespace std;

int tot;
clock_t start;

int main(){
    start = clock();//关于时间的神奇东东
    while (tot <= 2147483647){
        tot++;
        if (clock() - start >= 1.0 * CLOCKS_PER_SEC) {
            printf ("%d\n", tot);
            return 0;
        }
    }
    return 0;
}

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <time.h>
#include <cstring>
#include <queue>
#define Re register
using namespace std;

clock_t start;

const int maxn = 200100;

int n, m, u, v, w;

int cnt;
int head[maxn], dis[maxn];

struct Edge{
    int u, v, w, nxt;
    Edge(int _u, int _v, int _w, int _nxt){
        this -> u = _u;
        this -> v = _v;
        this -> w = _w;
        this -> nxt = _nxt;
    }
    Edge(){};
}e[maxn << 2];

struct node{
    int x, w;
    friend bool operator < (node a, node b){
        return a.x > b.x;
    }
};

priority_queue<node>Q;

void add (int u, int v, int w){
    e[++cnt] = Edge(u, v, w, head[u]);
    head[u] = cnt;
}

int f_;
char ch_;
template <class T>
    inline T read (T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        while (ch_ > '9' || ch_ < '0'){if (ch_ == '-') f_ = -1; ch_ = getchar();}
        while (ch_ >= '0' && ch_ <= '9') x_ = (x_ << 3) + (x_ << 1) + ch_ - 48, ch_ = getchar();
        return x_ *= f_;
    }

void Dijstra(){
    memset(dis, 0x3f, sizeof dis);
    dis[0] = 0;
    Q.push((node){0, 0});
    while (!Q.empty()){
        u = Q.top().x;
        Q.pop();
        for (Re int i = head[u];i;i = e[i].nxt){
            if (clock() - start >= 0.9*CLOCKS_PER_SEC){
                puts("-1");
                exit(0);
            }
            v = e[i].v;
            w = e[i].w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                Q.push((node){v, dis[v]});
            }
        }
    }
}

int main(){
    read(n);
    read(m);
    start = clock();
    for (Re int i = 0;i <= n; ++i){
        add (i, i + 1, 1);
        add (i + 1, i, 0);
    }
    for (Re int i = 1;i <= m; ++i){
        read(u); read(v);
        add (v, u - 1, -1);
        add (u - 1, v, 1);
    }
    Dijstra();
    printf ("%d\n", dis[n]);
    return 0;
}

关于查分约束

最大值，跑最短路
建边方法：  a-b <= c     b --> a建一条w为c的边
            a-b >= c     a --> b建一条w为-c的边

最小值，跑最长路
建边方法：  a-b >= c     b --> a建一条w为c的边
            a-b <= c     a --> b建一条w为-c的边

P1144 最短路计数

最小生成树

两个最小生成树算法, 都有一个共同的思想: 这棵树是一点一点长大的; 并且每次生长, 都是贪心的.

不同之处是: Kruscal算法是以边为中心的, 每次找最小的并且有用的边添加到树上;

Prim算法是以点为中心的, 每次找离树最近的点添加到树上.

Prim算法的优势: 稠密图, 尤其是完全图. 因为在Kurscal算法中, 必须事先求出所有边的长度才能
对之排序. 但是一个有5000节点的完全图, 这样做的空间开销是巨大的. Prim算法只在更新点到树的
距离时需要用到边长, 因此对于这种给坐标的完全图, 可以现用现算.

Prim的思想是将任意节点作为根，再找出与之相邻的所有边（用一遍循环即可），再将新节点更新并以此
节点作为根继续搜，维护一个数组：dis，作用为已用点到未用点的最短距离。

Prim算法之所以是正确的，主要基于一个判断：对于任意一个顶点v，连接到该顶点的所有边中的一条最短
边(v, vj)必然属于最小生成树（即任意一个属于最小生成树的连通子图，从外部连接到该连通子图的所有
边中的一条最短边必然属于最小生成树）

//普通Prim

//堆优化Prim

P1265 公路修建

这道题只能用prim

code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

const int maxn = 5010;
const double inf = 2147483647;

int n, k;
bool v[maxn];
double ans, minn;
double x[maxn], y[maxn], d[maxn];

int w;
char ch;
template <class T>
    T read(T &x){
        x = 0, w = 1, ch = getchar();
        while (ch > '9' || ch < '0'){if(ch == '-') w = -1; ch = getchar();}
        while (ch >= '0' && ch <= '9') x = (x<<3)+(x<<1)+ch-48, ch = getchar();
        return x *= w;
    }

double dis(double x,double y,double x1,double y1){
    return sqrt((double)(x-x1)*(x-x1) + (double)(y-y1)*(y-y1));
}

int main(){
    read(n);
    for (int i =  1;i <= n; ++i) {
        scanf("%lf%lf", &x[i], &y[i]);
    }
//  memset(d,0x7f,sizeof(d)); 
    for(int i=0;i<=n;i++) d[i]=inf;
    d[1]=0;
    for (int i = 1;i <= n; ++i){
        k = 0;
        minn =  inf;
        for (int j = 1;j <= n; ++j)
            if(!v[j] && d[j] < minn){
                minn = d[j];
                k = j;
            }
        v[k] = 1;
        ans += d[k];
        for (int j = 1;j <= n; ++j){
            if(!v[j] && dis(x[k], y[k], x[j], y[j]) < d[j]) d[j] = dis(x[k], y[k], x[j], y[j]);
        }
    }   
    printf("%.2lf", ans);
    return 0;
}

数的直径

两种求直径的方法:

在树上随机选一个点，对他进行一次dfs求出距离它距离最远的一个点A,然后再用那一个点dfs回来找到一个离A点距离最远的B点，AB之间的路径即为树的直径 $code

void Dfs (int x, int f, int len){
    if (len > maxx) maxx = len, qwq = x;
    fa[x] = f;
    for (int i = head[x]; i;i = e[i].nxt){
        if (e[i].v == f) continue;
        Dfs (e[i].v, x, len+1);
    }
}
maxx = inf;
Dfs(1, 1, 0);
from = qwq; maxx = 0;
Dfs(from, 0, 0);
to = qwq;

$code

void Dfs (int x, int fa){
    for (Re int i = head[x]; i;i = e[i].nxt){
        if (e[i].v == fa) continue;
        Dfs (e[i].v, x);
        int len = 0;
        len = Max(len, f[x] + f[e[i].v] + 1);
        f[x] = Max(f[x], f[e[i].v] + 1);
    }
}

窝滴写法

code

int Dfs (int x, int f){
    int sum1 = 0, sum2 = 0;
    for (int i = head[x]; i;i = e[i].nxt){
        if (e[i].v == f) continue;
        sum2 = Max(sum2, Dfs(e[i].v, x) + 1);
        if (sum2 > sum1) swap(sum1, sum2);
    }
    ans = Max(sum1 + sum2, ans);
    return sum1;
}

SP1437 PT07Z - Longest path in a tree

板子题，随便求个直径就阔以了

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Re register
using namespace std;

const int maxn = 10010;

int n, u, v;
int cnt, ans;
int head[maxn];

int f_;
char ch_;
template<class T>
    inline T read(T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        for (; ch_ > '9' || ch_ < '0'; ch_ = getchar()) if (ch_ == '-') f_ = -1;
        for (; ch_ >= '0' && ch_ <= '9'; ch_ = getchar()) x_ = (x_ << 3) + (x_ << 1) + ch_ - 48;
        return x_ *= f_;
    }

inline int Max (int x,int y){return (x > y) ? x : y;}

struct Edge{
    int u, v, nxt;
    Edge (int _u, int _v, int _nxt){
        this -> u = _u; this -> v = _v;this -> nxt = _nxt;
    }Edge(){};
}e[maxn << 1];

void Add (int u, int v){
    e[++cnt] = Edge(u, v, head[u]);
    head[u] = cnt;
}

int Dfs (int x, int f){
    int sum1 = 0, sum2 = 0;
    for (Re int i = head[x]; i; i = e[i].nxt){
        if (e[i].v == f) continue;
        sum2 = Max(sum2, Dfs(e[i].v, x)+1);
        if (sum2 > sum1) swap(sum2, sum1);
    }
    ans = Max(ans, sum2 + sum1);
    return sum1;
}

int main(){
    read(n);
    for (Re int i = 1;i < n; ++i){
        read(u); read(v);
        Add(u, v); Add (v, u);
    }
    Dfs(1, 1);
    printf("%d\n", ans);
    return 0;
}

P3629 [APIO2010]巡逻

一道树的直径的好练习题，思路窝没想到....

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Re register
using namespace std;

const int maxn = 100100;

int n, k, u, v;
int cnt, maxx, start, ennd, qwq, mmp, ans;
int head[maxn], fa[maxn], f[maxn];
bool vis[maxn];

int f_;
char ch_;
template<class T>
    inline T read(T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        for (; ch_ > '9' || ch_ < '0'; ch_ = getchar()) if (ch_ == '-') f_ = -1;
        for (; ch_ >= '0' && ch_ <= '9'; ch_ = getchar()) x_ = (x_ << 3) + (x_ << 1) + ch_ - 48;
        return x_ *= f_;
    }

inline int Max(int x, int y){return (x > y) ? x : y;}

struct Edge{
    int u, v, nxt;
    Edge(int _u, int _v, int _nxt){
        this -> u = _u; this -> v = _v;
        this -> nxt = _nxt;
    }Edge(){};
}e[maxn << 1];

void Add (int u, int v){
    e[++cnt] = Edge(u, v, head[u]);
    head[u] = cnt;
}

void Dfs (int x, int f, int len){
    if (len > maxx) maxx = len, qwq = x;
    fa[x] = f;
    for (Re int i = head[x]; i;i = e[i].nxt){
        if (e[i].v == f) continue;
        Dfs (e[i].v, x, len+1);
    }
}

int Dfss (int x, int f){
    int sum1 = 0, sum2 = 0;
    for (Re int i = head[x]; i; i = e[i].nxt){
        if (e[i].v == f) continue;
        int qaq = 1;
        if (vis[x] && vis[e[i].v]) qaq = -1;
        sum2 = Max(sum2, Dfss (e[i].v, x) + qaq);
        if (sum2 > sum1) swap(sum2, sum1);
    }
    mmp = Max (sum1 + sum2, mmp);
    return sum1;
}

/*void Dfss (int x, int _f){
    for (Re int i = head[x]; i; i = e[i].nxt){
        if (e[i].v == _f) continue;
        Dfss (e[i].v, x);
        int qaq = 1;
        if (vis[x] && vis[e[i].v]) qaq = -1;
        mmp = Max (mmp, f[x] + f[e[i].v] + qaq);
        f[x] = Max (f[x], f[e[i].v] + mmp);
    }
}*/

int main(){
    read(n);
    read(k);
    for (Re int i = 1;i < n; ++i){
        read(u); read(v);
        Add (u, v); Add (v, u);
    }
    Dfs (1, 0, 0);
    start = qwq, maxx = 0;
    Dfs (start, 0, 0);
    ennd = qwq;
    ans = ((n-1) << 1) - maxx + 1;
    if (k == 1){
        printf ("%d\n", ans);
        return 0;
    }
    while (ennd != 0){
        vis[ennd] = 1;
        ennd = fa[ennd];
    }
    Dfss (1, 0);
    ans = ans - mmp + 1;
    printf ("%d\n", ans);
    return 0;
}

Tarjan

4142. 抗震救灾

~~此题无来源~~
近日，由于一场世纪大地震，Planeptune 通讯设施全面瘫痪。在灾后重建中，抢修通讯设备成为首要任务。现在，作为首席工程师的你
已经了解该国的基本状况，Neptune 希望你设计一种方案，使得所用的救灾资金尽可能少。 已知该国地形可以简化成包含  个点的一张
无向图，每个点代表一座城市。由于地震的破坏，该国的城市之间已经只剩下  条仍具备通行条件的双向道路。当然，目前该国的所有城
市是联通的。现在，Neptune 希望在一些仍能通行的道路下铺设通信电缆，使得任意两个城市之间能够通过通信电缆直接或间接地传递灾
情。不过，若某条道路被破坏后，该国的所有城市不再全部联通，则这条道路被认为是危险道路，因为一旦这条道路被次生灾害破坏，那
么相应的通信电缆也会被破坏，而且没有其他可供选择的途径来恢复通信。在这样的危险道路上，你只能选择用无线通信设备代替。
（注意：在非危险道路上，即使无线设施的费用低于通信电缆的费用，你也只能铺设通信电缆，因为这种方式可靠性更高。）

输入格式：
第一行包含两个正整数n和m。
接下来共m行，第i行包含四个整数 s[i]，t[i]，a[i]和b[i]，分别表示第i条道路连接的两座城市，以及在该条道路上铺设电缆和架
设无线设备的费用。

输出格式：
第一行包含一个整数，表示最小代价。

用 Tarjan 算法把桥求出来，显然桥只能用无线，然后求最小生成树（有重边，但排序时选了val最小的）

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;

const int maxn = 5e5 + 10;

int n, m, u, v, w, a, b, fx, fy;
int tim, top, cnt, ans, edge_num = 1;
int head[maxn], low[maxn], dfn[maxn], fa[maxn], bridge[maxn << 1];

struct Edge{
    int from, to, vala, valb, next;
}edge[maxn << 1];

struct node{
    int u, v, w;
    bool friend operator < (node x, node y){
        return x.w < y.w;
    }
}e[maxn << 1];

int f_;
char ch_;
template <class T>
    inline T read (T &x_){
        x_ = 0, f_ = 1, ch_ = getchar();
        while (ch_ > '9' || ch_ < '0'){if (ch_ == '-') f_ = -1; ch_ = getchar();}
        while (ch_ >= '0' && ch_ <= '9') x_ = (x_ << 3) + (x_ << 1) + ch_ - 48, ch_ = getchar();
        return x_*f_;
    }

inline int Min (int x, int y){
    if (x > y) return y;
    return x;
}   

void add_edge (int u, int v, int a, int b){
    edge[++edge_num].from = u;
    edge[edge_num].to = v;
    edge[edge_num].vala = a;
    edge[edge_num].valb = b;
    edge[edge_num].next = head[u];
    head[u] = edge_num;
    return ;
}

void Tarjan (int x, int in_edge){
    dfn[x] = low[x] = ++tim;
    for (register int i = head[x]; i ;i = edge[i].next){
        int y = edge[i].to;
        if (!dfn[y]){
            Tarjan (y, i);
            low[x] = Min (low[x], low[y]);
            if (low[y] > dfn[x])
                bridge[i] = bridge[i ^ 1] = true;
        }
        else if (i != (in_edge ^ 1))
                low[x] = Min (low[x], dfn[y]);
    }
}

int get (int x){
    if (x == fa[x]) return x;
    return fa[x] = get (fa[x]);
}

signed main(){
    ios::sync_with_stdio(false);
    read(n);
    read(m);
    for (register int i = 1;i <= m; ++i){
        read(u);
        read(v);
        read(a);
        read(b);
        add_edge (u, v, a, b);
        add_edge (v, u, a, b);
    }
    for (register int i = 1;i <= n; ++i){
        if (!dfn[i]) Tarjan (i, 0);
    }
    /*for (register int i = 2;i <= edge_num; i += 2){
        if (bridge[i]) cout << i <<" "<<(i ^ 1)<<'\n';
    }*/
    for (register int i = 1;i <= n; ++i) fa[i] = i;
    for (register int i = 2;i <= edge_num; i += 2) {
        u = edge[i].from;
        v = edge[i].to;
        e[++cnt].u = u;
        e[cnt].v = v;
        if (bridge[i]) e[cnt].w = edge[i].valb;
        else e[cnt].w = edge[i].vala;
    }
    sort (e + 1, e + m + 1);
    for (register int i = 1;i <= m; ++i){
        fx = get (e[i].u);
        fy = get (e[i].v);
        if (fx == fy) continue;
        fa[fx] = fy;
        ans += e[i].w;
        cnt++;
        if (cnt == n-1) break;
    }
    cout << ans << '\n';
    return 0;
}

图论小结

最短路

根据题意建双向边，倒着跑一边最短路（重点的dis为100），利率为(1-z/(100.0)，ok

正反各跑一遍最短路即可

看完知道查分约束，不会写诶。。然后看题解，神TM一群dp dalao，只有个别dalao写了查分约束，然后学到了时间判负环QwQ

最小生成树

这道题只能用prim

数的直径

板子题，随便求个直径就阔以了

一道树的直径的好练习题，思路窝没想到....

最近公共祖先

Tarjan

用 Tarjan 算法把桥求出来，显然桥只能用无线，然后求最小生成树（有重边，但排序时选了val最小的）

二分图