Summer training camp-week2 graph theory

暑假集训-week2图论

A - Desert King

最优比例生成树+01规划
怎么说,,,,,
现学的,A bit out of range

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
// https://vjudge.net/contest/506494#problem/A
// 最优比例生成树+01分数规划+prim算法+实数二分
int n;
struct node
{
    
    double x;
    double y;
    double h;
} point[10010];
double graph[10010][10010]; //原图,represents the distance between points
double cost[10010][10010];  //表示代价,即高度
bool visit[10010];
double dis[10010];
double prim(double tar)
{
    
    double ans = 0;
    memset(visit, 0, sizeof(visit));
    for (int i = 1; i <= n; i++) //The outer loop must ben！因为ansAdd all distances！
        dis[i] = 0x3f3f3f3f;
    dis[1] = 0;
    for (int i = 1; i <= n; i++)
    {
    
        int x = -1;
        for (int j = 1; j <= n; j++)
        {
    
            if (!visit[j] && (x == -1 || dis[j] < dis[x]))
                x = j;
        }
        visit[x] = 1;
        ans += dis[x]; //Total distance update
        for (int j = 1; j <= n; j++)
            if (x != j)
                dis[j] = min(dis[j], cost[x][j] - tar * graph[x][j]);
    }
    return ans;
}
int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    while (cin >> n)
    {
    
        if (n == 0)
            break;
        for (int i = 1; i <= n; i++)
        {
    
            cin >> point[i].x >> point[i].y >> point[i].h;
        }
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
            {
    
                graph[i][j] = graph[j][i] = sqrt((point[i].x - point[j].x) * (point[i].x - point[j].x) + (point[i].y - point[j].y) * (point[i].y - point[j].y)); //距离差
                cost[i][j] = cost[j][i] = fabs(point[i].h - point[j].h);                                                                                         //高度差
            }
        double l = 0, r = 1e5;
        while (r - l > 1e-5)
        {
    
            double mid = (l + r) / 2;
            if (prim(mid) >= 0)
            {
    
                l = mid;
            }
            else
            {
    
                r = mid;
            }
        }
        printf("%.3f\n", r);
    }
    return 0;
}

P - 最小生成树

克鲁斯卡尔算法

#include <bits/stdc++.h>
using namespace std;
struct node
{
    
    int s;
    int e;
    int cost;
} path[200020];
int fa[5010];
int n, m;
bool cmp(node a, node b)
{
    
    return a.cost < b.cost;
}
int find(int x)
{
    
    if (fa[x] != x)
        return fa[x] = find(fa[x]);
    else
        return fa[x];
}
void connect(int x, int y)
{
    
    fa[find(x)] = fa[find(y)];
}
int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
    
        cin >> path[i].s >> path[i].e >> path[i].cost;
    }
    sort(path + 1, path + 1 + m, cmp);
    int cnt = 0;
    long long ans = 0;
    for (int i = 1; i <= m; i++)
    {
    
        int s = path[i].s;
        int e = path[i].e;
        if (find(s) != find(e))
        {
    
            ans += path[i].cost;
            connect(s, e);
            cnt++;
        }
        if (cnt == n - 1)
        {
    
            cout << ans << endl;
            return 0;
        }
    }
    cout << "orz" << endl;
    return 0;
}

Q - 单源最短路径（标准版）

#include <bits/stdc++.h>
using namespace std;
// 迪杰斯特拉(堆优化)
// https://www.luogu.com.cn/problem/P4779#submit
const int maxn = 100010, maxn2 = 500010;
int head[maxn], dis[maxn], cnt;
bool visit[maxn];
int n, m, s;
struct edge
{
    
    int to, dis, next;
} e[maxn2];
void add(int u, int v, int d)
{
    
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
struct node
{
    
    int dis;
    int pos;
    bool operator<(const node &x) const
    {
    
        return x.dis < dis;
    }
};
priority_queue<node> q;
int main()
{
    
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; ++i)
        dis[i] = 0x7fffffff;
    for (int i = 1; i <= m; i++)
    {
    
        register int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        add(u, v, d);
    }
    dis[s] = 0;
    q.push((node){
    0, s});
    while (!q.empty())
    {
    
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if (visit[x])
            continue;
        visit[x] = 1;
        for (int i = head[x]; i; i = e[i].next)
        {
    
            int y = e[i].to;
            if (dis[y] > dis[x] + e[i].dis)
            {
    
                dis[y] = dis[x] + e[i].dis;
                if (!visit[y])
                {
    
                    q.push((node){
    dis[y], y});
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}

R - 最近公共祖先（LCA）

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
// LCA问题
// https://www.luogu.com.cn/problem/P3379
int cnt, n, m, s;
int to[maxn], Next[maxn], head[maxn];
int d[maxn], f[maxn][20];
int t;
queue<int> q;
void add(int s, int e) //加边
{
    
    to[++cnt] = e, Next[cnt] = head[s], head[s] = cnt;
}
void bfs()
{
    
    q.push(s);
    d[s] = 1;
    while (q.empty() == false)
    {
    
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = Next[i])
        {
    
            int tar = to[i];
            if (d[tar])
                continue;
            d[tar] = d[x] + 1;

            f[tar][0] = x;
            for (int j = 1; j <= t; j++)
                f[tar][j] = f[f[tar][j - 1]][j - 1];
            q.push(tar);
        }
    }
}
int lca(int x, int y)
{
    
    if (d[x] > d[y])
        swap(x, y); //默认x小于y
    for (int i = t; i >= 0; i--)
        if (d[f[y][i]] >= d[x])
            y = f[y][i];
    if (x == y)
        return x;
    for (int i = t; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    t = (int)(log(n) / log(2)) + 1; //层数
    for (int i = 1; i < n; i++)
    {
    
        int s, e;
        cin >> s >> e;
        add(s, e);
        add(e, s);
    }
    bfs();
    for (int i = 1; i <= m; i++)
    {
    
        int a, b;
        cin >> a >> b;
        cout << lca(a, b)<<endl;
    }
    return 0;
}

S - 负环

#include <bits/stdc++.h>
using namespace std;
// 判断负环https://www.luogu.com.cn/problem/P3385
#define maxn 1000000
int T, n, m;
int to[maxn], edge[maxn], head[maxn], Next[maxn], cnt;
int dist[maxn];
bool visit[maxn];
int num[maxn]; //判断负环
queue<int> q;
void add(int x, int y, int z)
{
    
    to[++cnt] = y, edge[cnt] = z, Next[cnt] = head[x], head[x] = cnt;
}
int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
    
        bool flag = false;
        memset(visit, 0, sizeof(visit));
        memset(dist, 0x3f, sizeof(dist));
        memset(num, 0, sizeof(num));
        memset(head, 0, sizeof(head));
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
    
            int u, v, w;
            cin >> u >> v >> w;
            if (w >= 0)
            {
    
                add(u, v, w);
                add(v, u, w);
            }
            if (w < 0)
            {
    
                add(u, v, w);
            }
        }
        dist[1] = 0, visit[1] = 1;
        q.push(1);
        while (q.empty() == false)
        {
    
            int x = q.front();
            q.pop();
            visit[x] = 0;
            for (int i = head[x]; i; i = Next[i])
            {
    
                int y = to[i], z = edge[i];
                if (dist[y] > dist[x] + z)
                {
    
                    dist[y] = dist[x] + z;
                    num[y] = num[x] + 1; //This line and the followingnumJudgment is removedSPFA了
                    if (num[y] >= n)
                    {
    
                        flag = true;
                        break;
                    }
                    if (!visit[y])
                        q.push(y), visit[y] = true;
                }
            }
        }
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

T - 二分图最大匹配

#include <bits/stdc++.h>
using namespace std;
// 传送门;https://www.luogu.com.cn/problem/P3386
// 匈牙利算法
#define maxn 10000100
int n, m, e, ans;
bool f[1000][1000];
int to[maxn], Next[maxn], head[maxn], cnt;
int match[maxn];
bool visit[maxn];

void add(int x, int y)
{
    
    to[++cnt] = y, Next[cnt] = head[x], head[x] = cnt;
}
bool dfs(int x)
{
    
    for (int i = head[x]; i; i = Next[i])
    {
    
        int y = to[i];
        if (visit[y] == false)
        {
    
            visit[y] = true;
            if (!match[y] || dfs(match[y]))
            {
    
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++)
    {
    
        int u, v;
        cin >> u >> v;
        if (u <= n && v <= m)
            add(u, v);
    }
    ans = 0;
    for (int i = 1; i <= n; i++)
    {
    
        memset(visit, 0, sizeof(visit));
        if (dfs(i))
            ans++;
    }
    cout << ans << endl;
    return 0;
}