2/15 topology sorting +dfs (the order of specified directions is very important) +bfs

https://www.luogu.com.cn/problem/P1038
wa I got a point , At this point c[i]<=0 when , It cannot be transferred to the next layer

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+5;
int n,p,c[maxn],u,cnt,out[maxn],in[maxn],head[maxn];
bool vis[maxn],flag;
queue<int>q;
struct node
{
    
    int to,dis,nxt;
}e[maxn];
void add(int from,int to,int w)
{
    
    e[++cnt].to=to;
    e[cnt].dis=w;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}

int main()
{
    
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
    {
    
        scanf("%d%d",&c[i],&u);
        if(c[i]>0)
            q.push(i);
        else
            c[i]-=u;
    }
    for(int i=1;i<=p;i++)
    {
    
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        out[u]++;
        in[v]++;
    }
    while(!q.empty())
    {
    
        int u=q.front();q.pop();
        if(c[u]<=0)
            continue;
        for(int i=head[u];i;i=e[i].nxt)
        {
    
            int v=e[i].to;
            c[v]+=e[i].dis*c[u];
            in[v]--;
            if(!in[v])
                q.push(v);
        }
    }
    for(int i=1;i<=n;i++)
    {
    
        if(!out[i]&&c[i]>0)
        {
    
            printf("%d %d\n",i,c[i]);
            flag=1;
        }
    }
    if(!flag)
        cout<<"NULL"<<endl;
    return 0;
}

The general method is queu Is to find the smallest dictionary order to meet the requirements of the topic topological sequence
This question adopts priority queue , Reverse construction , Construct a reverse queue with the largest lexicographic order .
Because the question requires you to put the small number forward as far as possible , So the answer is not necessarily the smallest dictionary order . however , Put the small number forward as far as possible , Such a large number will naturally go as far as possible , thus , If the topological order is reversed , Then the inverse topological order with the largest lexicographic order must be the optimal solution . therefore , We can build a backgraph to find the topological order with the largest dictionary order , Finally, output in reverse order . （ quote ）

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+5;
int n,m,p,c[maxn],u,cnt,in[maxn],head[maxn],ans[maxn],g;
bool vis[maxn],flag;
priority_queue<int>q;
struct node
{
    
    int to,nxt;
}e[maxn];
void add(int from,int to)
{
    
    e[++cnt].to=to;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
void clean()
{
    
    memset(head,0,sizeof(head));
    memset(in,0,sizeof(in));
    memset(c,0,sizeof(c));
    memset(ans,0,sizeof(ans));
    cnt=0;g=0;
    while(!q.empty()) q.pop();
}
int main()
{
    
    int t;scanf("%d",&t);
    while(t--)
    {
    
        clean();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
    
            int u,v;scanf("%d%d",&u,&v);
            add(v,u);in[u]++;
        }
        for(int i=1;i<=n;i++)
            if(!in[i]) q.push(i);
        while(!q.empty())
        {
    
            int u=q.top();q.pop();
            ans[++g]=u;
            for(int i=head[u];i;i=e[i].nxt)
            {
    
                int v=e[i].to;
                in[v]--;
                if(!in[v]) q.push(v);
            }
        }
        if(g<n)
            printf("Impossible!\n");
        else{
    
            for(int i=n;i>=1;i--)
            {
    
                printf("%d ",ans[i]);
            }
            cout<<endl;
            }
    }
    return 0;
}

P6145 [USACO20FEB]Timeline G
https://www.luogu.com.cn/problem/P6145
Adopt queue optimization , Read in as 0 Put the points in the queue
Approval code ：a[v]=max(a[v],a[u]+e[i].dis); This node was first created in a[v] Days to complete , Or the precursor node + The number of days specified in the question

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e6+5;
struct node
{
    
    int to,dis,nxt;
}e[maxn];
int a[maxn],head[maxn],in[maxn],cnt,n,m,c;
void add(int from,int to,int w)
{
    
    e[++cnt].to=to;
    e[cnt].dis=w;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
queue<int>q;

int main()
{
    
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=n;i++)
    {
    
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=c;i++)
    {
    
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);in[v]++;
    }
    for(int i=1;i<=n;i++)
        if(!in[i])
            q.push(i);
    while(!q.empty())
    {
    
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
    
            int v=e[i].to;
            a[v]=max(a[v],a[u]+e[i].dis);
            in[v]--;
            if(!in[v])
                q.push(v);
        }
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<endl;
    return 0;
}

https://www.luogu.com.cn/record/69439301

#include <bits/stdc++.h>
#define y1 y11
using namespace std;
const int maxn=105;
const int inf=0x3f3f3f3f/2;
int n,mp[maxn][maxn],x1,y1,x2,y2,ans=inf;
int dx[4]={
    1,0,-1,0};
int dy[4]={
    0,-1,0,1};
bool flag;
void dfs(int x,int y,int dir,int k)
{
    
    if(k>=ans)
        return ;
    if(x==x2&&y==y2)
    {
    
        ans=min(ans,k);flag=1;return ;
    }
    for(int i=0;i<4;i++)
    {
    
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<=0||xx>n||yy<=0||yy>n)
            continue;
        if(!mp[xx][yy])
        {
    
            mp[xx][yy]=-1;
            int d=0;
            if(dir!=i) d=1;     // In different directions , It means you will turn , This cycle 0,1,2,3 All represent one direction 
            if(dir==-1) d=0;   // Initial value of processing direction 
            dfs(xx,yy,i,k+d);
            mp[xx][yy]=0;
        }
    }
}
int main()
{
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    
        for(int j=1;j<=n;j++)
        {
    
            char c;
            cin>>c;
            if(c=='A') x1=i,y1=j,mp[i][j]=1;
            else if(c=='B') x2=i,y2=j,mp[i][j]=0;
            else if(c=='x') mp[i][j]=-1;
        }
    }
    dfs(x1,y1,-1,0);
    if(flag)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

A very good search topic .
https://www.luogu.com.cn/problem/P2049

#include <bits/stdc++.h>

using namespace std;
int m,n,k,mp[105][105],ans;
bool vis[105],used[105][105][105];
int dx[2]={
    1,0};
int dy[2]={
    0,1};
struct node
{
    
    int x,y,val;
};
queue<node>q;
void bfs()
{
    
    node cur,nxt;
    q.push({
    1,1,mp[1][1]});
    while(!q.empty())
    {
    
        cur=q.front();q.pop();
        int x=cur.x,y=cur.y,w=cur.val;
        if(x==m&&y==n)
        {
    
            vis[w]=1;
            continue;
        }
        for(int i=0;i<2;i++)
        {
    
            int nx=x+dx[i],ny=y+dy[i];
            int nw=(mp[nx][ny]*w)%k;
            if(nx<=0||nx>m||ny<=0||ny>n||used[nx][ny][nw])
                continue;
            q.push({
    nx,ny,nw});
            used[nx][ny][nw]=1;
        }
    }
    for(int i=0;i<k;i++)
    {
    
        if(vis[i]) ans++;
    }
    cout<<ans<<endl;
    for(int i=0;i<k;i++)
    {
    
        if(vis[i]) cout<<i<<" ";
    }
    cout<<endl;
}
int main()
{
    
    scanf("%d%d%d",&m,&n,&k);
    for(int i=1;i<=m;i++)
    {
    
        for(int j=1;j<=n;j++)
            scanf("%d",&mp[i][j]),
            mp[i][j]%=k;
    }
    bfs();
    return 0;
}