P2500题解

· · 题解

题外话

暴力碾标算

思路 & Coding

其实这一题非常的简单

首先,使用结构体来存储边

struct node
{
    int u;
    int v;
    int w;
}e[500010];

然后，用一个数组 fa[] 来储存=这一个点所属的合集

接着，如果输入让我们改变某一个点 x 的阵营

我们只需要将 fa[x] 改成目标阵营即可

如果他让我们求最小边权，我们就把 m 个边全都扫一遍

将所有符合条件的边的边权取一个 min 即可

void query(int num_1,int num_2)
{
    int minn = INT_MAX;
    for(int i = 1;i <= tot;i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        if(fa[u] == num_1 and fa[v] == num_2) minn = min(minn,w);
        if(fa[v] == num_1 and fa[u] == num_2) minn = min(minn,w);
    }
    if(minn == INT_MAX) printf("No Found!\n");
    else printf("%lld\n",minn);
}

于是，代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
   register int s = 0,w = 1;
   register char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

int tot;
int n,m,q;
int fa[500010];

struct node
{
    int u;
    int v;
    int w;
}e[500010];

void query(int num_1,int num_2)
{
    int minn = INT_MAX;
    for(int i = 1;i <= tot;i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        if(fa[u] == num_1 and fa[v] == num_2) minn = min(minn,w);
        if(fa[v] == num_1 and fa[u] == num_2) minn = min(minn,w);
    }
    if(minn == INT_MAX) printf("No Found!\n");
    else printf("%lld\n",minn);
}

signed main()
{
    for(int i = 1;i <= 500005;i++) fa[i] = 1;
    n = read();
    m = read();
    for(int i = 1;i <= m;i++)
    {
        int u,v,w;
        u = read();
        v = read();
        w = read();
        e[++tot].u = u;
        e[tot].v = v;
        e[tot].w = w;
    }
    q = read();
    while(q--)
    {
        string s;
        int k;
        cin >> s;
        if(s == "MoveA")
        {
            scanf("%lld",&k);
            fa[k] = 1;
        }
        else if(s == "MoveB")
        {
            scanf("%lld",&k);
            fa[k] = 2;
        }
        else if(s == "MoveC")
        {
            scanf("%lld",&k);
            fa[k] = 3;
        }
        else if(s == "AskAA") query(1,1);
        else if(s == "AskAB") query(1,2);
        else if(s == "AskAC") query(1,3);
        else if(s == "AskBB") query(2,2);
        else if(s == "AskBC") query(2,3);
        else if(s == "AskCC") query(3,3);
    }
    return 0;
}

接着，恭喜您，TLE了！

妙啊

这时候，我们要想着如何优化

首先看修改操作

但显然 O(1) 无法优化了

那我们想一想在搜索边的时候如何缩小

题目要求的是:

询问两个端点分别属于 x 集合和 y 集合的所有边中最小的权值是多少。

那么，我们就设想，如何使我们找到第一个符合要求的边就是最小的边

答案很显然：先把边排序一边

这样能极大程度缩小遍历的范围

So，AC Coding:

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
   register int s = 0,w = 1;
   register char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

int n,m,q;
int fa[500010];

struct node
{
    int u;
    int v;
    int w;
}e[500010];

bool cmp(node x,node y)
{
    return x.w < y.w;
}

void query(int num_1,int num_2)
{
    int minn = INT_MAX;
    for(int i = 1;i <= m;i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        if(fa[u] == num_1 and fa[v] == num_2)
        {
            minn = min(minn,w);
            break;
        }
        if(fa[v] == num_1 and fa[u] == num_2)
        {
            minn = min(minn,w);
            break;
        }
    }
    if(minn == INT_MAX) printf("No Found!\n");
    else printf("%lld\n",minn);
}

signed main()
{
    for(int i = 1;i <= 500005;i++) fa[i] = 1;
    n = read();
    m = read();
    for(int i = 1;i <= m;i++)
    {
        int u,v,w;
        u = read();
        v = read();
        w = read();
        e[i].u = u;
        e[i].v = v;
        e[i].w = w;
    }
    sort(e + 1,e + m + 1,cmp);
    q = read();
    while(q--)
    {
        string s;
        int k;
        cin >> s;
        if(s == "MoveA") k = read(),fa[k] = 1;
        else if(s == "MoveB") k = read(),fa[k] = 2;
        else if(s == "MoveC") k = read(),fa[k] = 3;
        else if(s == "AskAA") query(1,1);
        else if(s == "AskAB") query(1,2);
        else if(s == "AskAC") query(1,3);
        else if(s == "AskBB") query(2,2);
        else if(s == "AskBC") query(2,3);
        else if(s == "AskCC") query(3,3);
    }
    return 0;
}