头像

明日原由纪




离线:5小时前


最近来访(12)
用户头像
辣鸡号航母
用户头像
胡尔摩斯
用户头像
straySheep.
用户头像
LH_95
用户头像
终极殺人王
用户头像
AcWing2AK
用户头像
lscll
用户头像
ssyyg11
用户头像
仲冬的烟火
用户头像
潘潘_the_panda
用户头像
长小圆

新鲜事 原文

AcWing《蓝桥杯集训·每日一题》拼团优惠!https://www.acwing.com/activity/content/introduction/2869/group_buy/122085/



#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=200010;
int h[N],ne[M],e[M],idx; //存储邻接表
int n,m;
int color[N]; //表示每个点所染的颜色

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool dfs(int u, int c)
{
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i]) //遍历与当前有关的所有根节点
    {
        int j = e[i];
        if (!color[j]) //若当前根节点没有染过色,就给他染色
        {
            if(!dfs(j,3-c)) return false;
        }
        else if( color[j] == c) return false; //如果当前的根节点与当前的点的颜色相同则矛盾
    }
    return true;
}
int main()
{
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--)
    {
        int a , b; 
        cin >> a >> b;
        add(a,b),add(b,a);    
    }
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    if (flag) puts("Yes");
    else puts("No");
    return 0;
}



并查集的简单运用

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010,INF=0x3f3f3f3f;
int p[N];
int n,m;
struct Edge
{
    int a,b,w;
    bool operator<(const Edge &W)const
    {
        return w<W.w;
    }
}edges[N];
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int kruskal() //根据权重排序所有边+并查集的简单运用
{
    sort(edges,edges+m);
    //初始化并查集
    for(int i=1;i<=n;i++) p[i]=i;

    int res=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;

        a=find(a),b=find(b);
        if(a!=b)
        {
            p[a]=b;
            res+=w;
            cnt++;
        }
    }
    if(cnt<n-1) return INF;
    else return res;
}
int main()
{
    cin >> n >>m;

    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin >>a >>b >>w;
        edges[i]={a,b,w};
    }

    int t=kruskal();

    if(t==INF) puts("impossible");
    else printf("%d\n",t);

    return 0;
}



#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int n,m;
bool st[N];
int dist[N];
int g[N][N];

int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];
        st[t]=true;

        for(int j=1;j<=n;j++)
        dist[j]=min(dist[j],g[t][j]); //更新点到集合的最小距离
    }
    return res;
}

int main()
{
    cin >>n >>m;
    memset(g,0x3f,sizeof g);

    while(m--)
    {
        int a,b,c;
        cin >>a >>b >>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
    if(t==INF) puts("impossible");
    else printf("%d\n",t);
    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=10010,M=2010;
int ne[N],w[N],e[N],idx,cnt[N],dist[N],h[M];
bool st[N];
int n,m;
bool spfa()
{
    queue<int> q;

    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=true; //所有的元素都在队列中
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false; //表示该点不在队列中
        //与正常的spfa求差不多
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i]) //只有出现负权边的时侯才会进行更新否则输出全为0,这就是dist数组初始化为0的原因
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;

                if(cnt[j]>=n) return true;
                if(!st[j]) //首先它得是存在于负权欢中,它才能再次进入队列
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m;
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;
int h[N];
int e[N],ne[N],w[N],idx;
int n,m;
bool st[N];
int dist[N];
int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false; //表示出队
        for(int i=h[t];i!=-1;i=ne[i]) //用队头元素更新与其相关的边 
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i]) //松弛
            {
                dist[j]=dist[t]+w[i];
                if(!st[j]) //如果被更新后的点比之前更小了,则进入队列更新与之相关的点
                {
                 q.push(j);
                 st[j]=true; //表示进入队列
                }
            }
        }
    }
    return dist[n];
}
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m ;
    while(m--)
    {
        int a,b,c;
        cin >>a >>b >>c;
        add(a,b,c);
    }
    auto t=spfa();
    if(t==0x3f3f3f3f) puts("impossible");
    else printf("%d\n",t);
    return 0;
}



//解决有限边限制的最短路 —— bellman-ford 算法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int backup[N],dist[N]; //backup数组的存在意义在于防止串联的发生也就是一次只更新一代的最短路,不会出现隔代的情况
struct Edge {
    int a, b, c;
} edge[M]; //记录所有边,每次迭代只需要遍历所有边
void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++)
        {
            auto t=edge[j];
            dist[t.b]=min(dist[t.b],backup[t.a]+t.c);
        }
    }
}
int main()
{
    cin >> n >> m  >> k;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin >>a >> b >> c;
        edge[i]={a,b,c};
    }
    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);
    return 0;
}


新鲜事 原文

AcWing【集日历瓜分10000AC币活动】赠送1月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/send/237675/1/ca8b1764/ AcWing【集日历瓜分10000AC币活动】赠送2月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/send/237675/2/13bdab4d/ AcWing【集日历瓜分10000AC币活动】赠送4月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/send/237675/4/7257d484/ AcWing【集日历瓜分10000AC币活动】赠送7月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/send/237675/7/b687d3c2/ AcWing【集日历瓜分10000AC币活动】赠送8月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/send/237675/8/d1078ea6/ AcWing【集日历瓜分10000AC币活动】赠送9月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/send/237675/9/eb0782ba/


新鲜事 原文

有没有佬给个10,AcWing【集日历瓜分10000AC币活动】求10月日历!https://www.acwing.com/file_system/gui/taskbar/widgets/clock/calendar/receive/237675/10/


活动打卡代码 AcWing 4729. 解密

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

int main()
{
    int k;
    scanf("%d", &k);

    while (k -- )
    {
        LL n, d, e;
        scanf("%lld%lld%lld", &n, &d, &e);
        LL m = n - e * d + 2;
        LL dt = m * m - 4 * n;
        LL r = sqrt(dt);

        if (dt < 0 || r * r != dt) puts("NO");
        else printf("%lld %lld\n", (m - r) / 2, (m + r) / 2);
    }

    return 0;
}