头像

AC_any




离线:4小时前



AC_any
12小时前

说明

  • 拓扑排序:每次取入度为零的点,拿走,更新其余的,出现新的入度为零入队、直到再没有入度为零的。如果全部访问则是完整的拓扑序,否则存在环。

c++

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

using namespace std;

class Adj{
public:
    typedef function<void(int i)> call_t;//拿函数做为参数
    Adj(){
        idx=0;
        memset(h,-1,sizeof h);//指向-1表示为空
    }

    void add(int from,int to){
        //头插法
        e[idx]=to;//放入新空间
        ne[idx]=h[from];//连接头结点的下一个节点,先连
        h[from]=idx;//头结点指向当前节点,后断
        idx++;//idx指向新的未分配的空间
    }

    //对now的下一个值,做func操作
    void nxt(int now,call_t func){
        for(int i=h[now];i!=-1;i=ne[i]){
            int nxt=e[i];
            func(nxt);
        }
    }

private:
    const static int N=100010;
    int h[N],e[N],ne[N],idx;
};


Adj adj;
const int N = 100010;
int n, m;
int d[N];//入度
int q[N];//队列

bool topsort()
{
    int hh = 0, tt = -1;

    //零入度节点入队
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;


    //依次出队
    while (hh <= tt)
    {
        int t = q[hh ++ ];

        adj.nxt(t,[&](int x){
            if(--d[x]==0) q[++tt]=x;
        });

    }

    return tt == n - 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        adj.add(a, b);
        d[b] ++ ;
    }

    if (!topsort()) puts("-1");
    else
    {
        //出队只是移动指针,其实数据还在
        for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
        puts("");
    }

    return 0;
}

匿名函数,几个例子

//对 a 数组中的元素进行排序,=表示拷贝传入,&是以引用方式传入,-> xxx 说明返回值类型
sort(num, num+4, [=](int x, int y) -> bool{ return x < y; } );

//可以为匿名函数命名,有点莫名其妙的操作
#include <iostream>
using namespace std;
int main()
{
    //display 即为 lambda 匿名函数的函数名
    auto display = [](int a,int b) -> void{cout << a << " " << b;};
    //调用 lambda 函数
    display(10,20);
    return 0;
}



AC_any
13小时前

思路

每条边的权重都是相同的正数,可以用bfs来求最短距离。

  • y总:开辟一个距离数组d,让每个第一次被访问到的节点记录当前的层数(即一号到自己的最短距离),最后,返回d[n]

  • 变化:我只维护一个当前层数,每次都把队列里的所有元素(即上一层的)取出,层数加加。注意,中间遇到n就直接返回当前层数加一。

  • 由于存在提前返回的情况,速度快一点。为了省劲儿我用了vector表示邻接表,数组描述应该可以更快。

my c++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>


using namespace std;
#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl

const int N = 100010,M=100010,INF=0x3f3f3f3f;
int n,m;

vector<int> adj[N];
int vis[N];

void init(){
    cin>>n>>m;
    ffor(i,0,m){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
    }

    /*test
    ffor(i,1,n+1){
        out(i);out("->");
        for(auto &x: adj[i]) out(x);
        nl;
    }
    */
}
bool pushNxt(int now,queue<int> &que){
    bool over=false;
    for(auto &x:adj[now]){
        if(x==n){
            over=true;
            break;
        }
        if(!vis[x]){
            vis[x]=1;
            que.push(x);
        }
    }
    return over;
}
int bfs(int s){

    int steps=0;
    vis[s]=1;
    queue<int> que;
    que.push(s);

    while(que.size()){

        //当前now--end_即上一层的全部元素
        int now=que.front();que.pop();
        int end_=que.back();

        while(now!=end_){
            if(pushNxt(now,que)) return steps+1 ;

            now=que.front();que.pop();
        }
        if(pushNxt(now,que)) return steps+1 ;

        //处理完上一层
        steps++;
    }

    return -1;
}


void acwing(){
    init();
    out(bfs(1));nl;
}

int main(){
    // init();
    acwing();
    return 0;
}

y总

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
    memset(d, -1, sizeof d);

    queue<int> q;
    d[1] = 0;
    q.push(1);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1)
            {
                //第一次访问到,比父亲的层数加一
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }

    return d[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}



活动打卡代码 AcWing 847. 图中点的层次

AC_any
13小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>


using namespace std;
#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl

const int N = 100010,M=100010,INF=0x3f3f3f3f;
int n,m;

vector<int> adj[N];
int vis[N];

void init(){
    cin>>n>>m;
    ffor(i,0,m){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
    }

    /*test
    ffor(i,1,n+1){
        out(i);out("->");
        for(auto &x: adj[i]) out(x);
        nl;
    }
    */
}
bool pushNxt(int now,queue<int> &que){
    bool over=false;
    for(auto &x:adj[now]){
        if(x==n){
            over=true;
            break;
        }
        if(!vis[x]){
            vis[x]=1;
            que.push(x);
        }
    }
    return over;
}
int bfs(int s){

    int steps=0;
    vis[s]=1;
    queue<int> que;
    que.push(s);

    while(que.size()){


        int now=que.front();que.pop();
        int end_=que.back();

        while(now!=end_){
            if(pushNxt(now,que)) return steps+1 ;

            now=que.front();que.pop();
        }
        if(pushNxt(now,que)) return steps+1 ;
        steps++;
    }

    return -1;
}


void acwing(){
    init();
    out(bfs(1));nl;
}

int main(){
    // init();
    acwing();
    return 0;
}




AC_any
3天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int x)//为x找对象
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];//取x的下一个节点
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                // j正好没有匹配或者让已经和j匹配的match[j]换一个备胎
                // 女孩j发现对象有备胎,就选择绿他,否则,坚定和他在一起
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d%d", &n1, &n2, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }



    int res = 0;
    for (int i = 1; i <= n1; i ++ )
    {
        /* st数组用来保证本次匹配过程中,第二个集合中的每个点只被遍历一次,防止死循环。
        match存的是第二个集合中的每个点当前匹配的点是哪个,
        但就算某个点当前已经匹配了某个点,也有可能被再次遍历,所以不能起到判重的作用。
        */
        memset(st, false, sizeof st);
        if (find(i)) res ++ ;//找到合法匹配
    }

    printf("%d\n", res);

    return 0;
}




AC_any
3天前

Y总代码

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

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
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])
        {
            //c>0就一定是1或2,取相反就是3-c
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

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

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b;
        scanf("%d%d", &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;
}





AC_any
3天前
r[nxt]==0){
            if(!dfs(nxt,3-c)) return false;
        }else if(color[nxt]==c) return false;
    }
    return true;
}


int main(){
    int n,m;
    cin>>n>>m;
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }


    bool flag=true;
    ffor(i,1,n+1){
        if(color[i]==0){
            if(!dfs(i,1)){
                flag=false;
                break;
            }
        }
    }
    flag ? puts("Yes"):puts("No");

    return 0;
}




AC_any
3天前
#include<iostream>
#include<algorithm>

using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)

//边数的上限更大
const int N=100010,M=200020,INF=0x3f3f3f3f;

struct edge{
    int a,b,w;
    bool operator<(const edge& t){
        return w<t.w;
    }
}e[M];

int n,m;

int p[N];
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int K(){
    sort(e,e+m);//边权由小到大

    ffor(i,1,n+1) p[i]=i;//初始化,每个点

    int cnt=0,sum=0;

    ffor(i,0,m){//从最小的边开始查找
        int a=find(e[i].a),b=find(e[i].b),w=e[i].w;

        if(a!=b){
            p[a]=b;//合并端点两侧的连通分量
            cnt++;//加入一条新边
            sum+=w;
        }
    }

    if(cnt<n-1) return INF;//无法连接所有点
    return sum;
}

int main(){
    cin>>n>>m;
    ffor(i,0,m) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);

    int t=K();
    t==INF? printf("impossible\n"):printf("%d\n",t);
    return 0;
}




AC_any
3天前

c++见注释

#include<iostream>
#include<algorithm>

using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)

//边数的上限更大
const int N=100010,M=200020,INF=0x3f3f3f3f;

struct edge{
    int a,b,w;
    bool operator<(const edge& t){
        return w<t.w;
    }
}e[M];

int n,m;

int p[N];
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int K(){
    sort(e,e+m);//边权由小到大

    ffor(i,1,n+1) p[i]=i;//初始化,每个点

    int cnt=0,sum=0;

    ffor(i,0,m){//从最小的边开始查找
        int a=find(e[i].a),b=find(e[i].b),w=e[i].w;

        if(a!=b){
            p[a]=b;//合并端点两侧的连通分量
            cnt++;//加入一条新边
            sum+=w;
        }
    }

    if(cnt<n-1) return INF;//无法连接所有点
    return sum;
}

int main(){
    cin>>n>>m;
    ffor(i,0,m) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);

    int t=K();
    t==INF? printf("impossible\n"):printf("%d\n",t);
    return 0;
}




AC_any
3天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl 

const int N=510;
const int INF=0x3f3f3f3f;

int n,m;

int g[N][N];
bool st[N];//当前是否在生成树里
int dist[N];

void init(){
    cin>>n>>m;

    memset(g,0x3f,sizeof g);

    while(m--){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        g[a][b]=g[b][a]=min(g[a][b],w);
    }
}

int prim(){
    memset(dist,0x3f,sizeof dist);

    int sum=0;
    //循环n轮找出生成树的所有节点
    ffor(i,0,n){
        //从待加入生成树的节点里(st[v]==0)找出一个最小的dist[nxti]
        int nxti=-1;
        ffor(v,1,n+1)
            if(!st[v]&&(nxti==-1||dist[nxti]>dist[v])) nxti=v;


        //生成树大于一条边,且同下一个节点不连通(不合法)
        if(i&&dist[nxti]==INF) return INF;

        //加入生成树
        st[nxti]=true;

        if(i) sum+=dist[nxti];

        //松弛操作,更新剩余待加入节点的到生成树的最小距离
        ffor(v,1,n+1) 
             if(!st[v]) dist[v]=min(g[nxti][v],dist[v]);
    }
    return sum;
}

void acwing(){
    init();
    int t=prim();
    t==INF ? printf("impossible\n"):printf("%d\n",t);
    return ;
}


int main(){


    acwing();
    return 0;
}




AC_any
3天前

注记

  • 如果要打印生成树,需要维护最短边(包括起点,终点),而不仅仅是终点到生成树的最短距离。
  • 更新树的权重,要在松弛操作之前,避免出现权重为负数的自环,改变已经加入生成树的节点的距离。

模板

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

using namespace std;


#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl 

const int N=510;
const int INF=0x3f3f3f3f;

int n,m;

int g[N][N];
bool st[N];//当前是否在生成树里
int dist[N];

void init(){
    cin>>n>>m;

    memset(g,0x3f,sizeof g);

    while(m--){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        g[a][b]=g[b][a]=min(g[a][b],w);
    }
}

int prim(){
    memset(dist,0x3f,sizeof dist);

    int sum=0;
    //循环n轮找出生成树的所有节点
    ffor(i,0,n){
        //从待加入生成树的节点里(st[v]==0)找出一个最小的dist[nxti]
        int nxti=-1;
        ffor(v,1,n+1)
            if(!st[v]&&(nxti==-1||dist[nxti]>dist[v])) nxti=v;


        //生成树大于一条边,且同下一个节点不连通(不合法)
        if(i&&dist[nxti]==INF) return INF;

        //加入生成树
        st[nxti]=true;

        if(i) sum+=dist[nxti];

        //松弛操作,更新剩余待加入节点的到生成树的最小距离
        ffor(v,1,n+1) 
             if(!st[v]) dist[v]=min(g[nxti][v],dist[v]);
    }
    return sum;
}

void acwing(){
    init();
    int t=prim();
    t==INF ? printf("impossible\n"):printf("%d\n",t);
    return ;
}


int main(){


    acwing();
    return 0;
}