2/15 拓扑排序+dfs(规定方向的顺序很重要）+bfs

https://www.luogu.com.cn/problem/P1038

wa了一个点，当这个点的c[i]<=0时，是不能传递到下一层的

#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;
}

           

一般的方法用queu的是求字典序最小的满足题目要求的拓扑序列

本题采用优先队列，反向建图，构造一个字典序最大的反向队列。

由于题目要求你把小的数尽量往前放，所以答案不一定是最小的字典序。但是，把小的数尽量往前放，那么大的数自然会尽量往后，这样一来，如果把拓扑序反过来，那么字典序最大的反拓扑序就一定是最优解。于是，我们可以建一个返图去求字典序最大的拓扑序，最后再倒序输出。 （引用）

#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

采用队列优化，将入读为0的点放到队列中

核定代码：

a[v]=max(a[v],a[u]+e[i].dis);

这个结点最早在a[v]天完成，或者前驱节点+题中规定的几天

#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;     //方向不一样，就说明会转向，这个的循环0，1，2，3都代表一个方向
            if(dir==-1) d=0;   //处理方向的初始值
            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;
}

           

一道非常好的广搜题目。

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;
}