解题报告 P1347 排序

题目内容

P1347

大意:给定若干个元素的偏序关系,求是否能判定排好序后序列的顺序。

如果根据前 i 个关系可以直接得到,输出序列并直接结束程序。

如果第 i 个关系造成了矛盾,输出 i 并结束程序。

如果根据所有的关系都不能还原序列,输出无法完成。

解题思路

看到偏序关系就想到利用图论建模然后跑拓扑排序,结果30分

说回正题:这题还是需要注意很多地方的,还是先来分析思路。

题目要求的是通过前 i 个来判断,因此我们要根据所有的关系挨个加边然后每加一次边跑一遍拓扑排序,由于 n\le26 所以不需要担心时间问题。

拓扑排序的实现有一些细节:首先显而易见的,如果给出来的偏序关系形成了环,那显然是不可以的,直接返回,判断是否有环的标准是拓扑排序能否遍历完所有给出的点,如果遍历不完,说明图存在环,直接输出矛盾即可。

但是遍历所有点并不代表就能形成完整的排序,有可能给出的是诸如下面的关系:

C

这样拓扑排序仍能遍历整张图,但是遍历的顺序不唯一,表明条件不足,所以我们要记录拓扑排序的深度 step,如果最终的深度刚好等于节点的个数才能判定排序的序列唯一。

还有要注意的就是存储入度的数组要每次重新开,不然会玄学 WA,而且这张图可能有自环与重边,所以存图的时候我使用的是 std::set,方便排除自环和重边的影响。

下面的拓扑排序函数返回值有三种:1 代表条件暂时不足,2 代表可以输出序列,0 代表出现矛盾条件。

注意 IO 的要求,防止被卡空格之类的事情出现,注意细节

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <set>
using namespace std;

set<int> g[27];//存边
set<int> all;//all是存储当前给出的所有点的集合

struct node
{
    int now,step;//now为当前节点,step为拓扑排序的深度
};

int n,m,depth;
string s;

int topo()
{
    s.clear();
    int ind[27];//重新处理入度数组
    memset(ind,0,sizeof(ind));//不memset的话会玄学
    for(auto i:all)
        for(auto j:g[i])
            ind[j]++;//处理
    queue<node> q;
    int visited=0;
    for(int i=1;i<=n;i++)
        if((!ind[i] && all.count(i)))//既要满足入度为0,也要满足点给出过
            q.push((node){i,1}),s.push_back(i+'A'-1);
    while(!q.empty())
    {
        visited++;
        int now=q.front().now,step=q.front().step;
        q.pop();
        for(auto i:g[now])
        {
            ind[i]--;
            if(!ind[i])
            {
                q.push((node){i,step+1});
                s.push_back(i+'A'-1);
                depth=max(depth,step+1);
            }
        }
    }
    if(depth==n)
        return 2;
    if(visited<all.size())
        return 0;
    return 1;
}

int main()
{
    scanf("%d %d",&n,&m);
    if(m<n-1)//这里是一个小优化:如果给出的关系不足n-1个是铁定完不成的
    {
        printf("Sorted sequence cannot be determined.\n");
        return 0;
    }
    char c[4];
    for(int i=1;i<=m;i++)
    {
        scanf("%s",c);
        int from=c[0]-'A'+1,to=c[2]-'A'+1;
        g[from].insert(to);
        all.insert(from),all.insert(to);
        int x=topo();
        if(x==0)
        {
            printf("Inconsistency found after %d relations.\n",i);
            return 0;
        }
        if(x==2)
        {
            printf("Sorted sequence determined after %d relations: ",i);
            cout<<s<<'.'<<endl;
            return 0;
        }
    }
    printf("Sorted sequence cannot be determined.\n");//如果前两种情况都没发生,那就是第三种了
    return 0;
}

解题报告 P4017 最大食物链计数

题目内容

P4017

大意:给出 mn 种生物的捕食关系,求最大食物链(最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者)的条数。

保证给定的关系没有环

解题思路

一看,无环,想到 DAG,然后又看到最大食物链的定义:

最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者

就想到了最大食物链的左端必然是入度为 0 的点,右端必然是出度为 0 的点,因此使用拓扑排序。

我们设 f_i 为从入度为 0 的所有点到达点 i 的方案数总和,由于拓扑排序是在一个点的信息更新完之后再入队的,所以正确性得到了保证。

具体的做法就是普通的拓扑排序,记录每个点的入度,然后从入度为 0 的点开始,使用顺推,对于处理到的每一个点入度都减一,然后方案数加上去,特别的,如果从队列中取出的这个点的出度为 0,则统计答案。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=5e3+5,p=80112002;
vector<int> g[maxn];
int n,m,ind[maxn],f[maxn],ans;

inline int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

void topo()
{
    queue<int> q;
    for(int i=1;i<=n;i++)//先扫一遍点,将入度为 0 的点加进去
        if(!ind[i])
            q.push(i),f[i]=1;//这里的初始状态很重要
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        if(g[now].size()==0)//如果出度为 0
        {
            ans=(ans+f[now])%p;//统计答案
            continue;
        }
        for(auto to:g[now])//遍历这个点的出边
        {
            f[to]=(f[to]+f[now])%p;//更新状态
            ind[to]--;//删边
            if(!ind[to])//如果这个点相连的信息都处理完了
                q.push(to);//入队
        }
    }
    return;
}

int main()
{
    n=read(),m=read();
    int a,b;
    for(int i=1;i<=m;i++)
    {
        a=read(),b=read();
        ind[a]++;//记录入度
        g[b].push_back(a);//加边
    }
    topo();//拓扑排序
    printf("%d\n",ans);
    return 0;
}

解题报告 P1038 神经网络(NOIP2003TG)

题目内容

P1038

大意:模拟一个神经网络,神经网络分层,每个节点有一个初始状态或者阈值,每个节点当状态大于0时向下层节点传递信息。

解题思路

注意读题

  • 输入神经元的入度一定为0
  • 输出神经元的出度一定为0
  • 边权可能为负
  • 如果没有大于0的输出层,记得输出NULL

因此这个图一定是个DAG,C_i的状态又需要上一个点的状态求解,故使用拓扑排序。

分析公式:

\begin{aligned}
C_i&=\sum_{(j,i\in E)}W_{j,i}C_j-U_i\
C_i+U_i&=\sum_{(j,i\in E)}W_{j,i}C_j
\end{aligned}

因此非输入层的节点的权值相当于要减去一个常数,故U_i没有必要存储,读入时判断即可

拓扑排序的思路仍然是判断这个点的入度并入队

代码:

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct Edge//边的结构体
{
    int from,to,dist;
};

const int maxn=106;
vector<Edge> g[maxn];//vector存图
int n,p,c[maxn],ind[maxn],oud[maxn];
//n,p见题意,ind存储入度,oud存储出度
queue<int> q;//拓扑排序时使用的队列

void ins(int u,int v,int w)//插入边
{
    g[u].push_back((Edge){u,v,w});
    return;
}

void topo()//拓扑排序函数
{
    while(!q.empty())//当队列不为空时
    {
        int now=q.front();
        q.pop();//记得pop
        for(auto &i:g[now])//C++11新特性
        {
            int to=i.to;
            if(c[now]>0)//如果当前节点的c值大于0
                c[to]+=c[now]*i.dist;//说明信息会继续传递下去,注意+=
            if(!--ind[to])//如果删掉该边后入度为0
                q.push(to);//那么你也可以入队了
        }
    }
    return;
}

int main()
{
    scanf("%d %d",&n,&p);
    for(int i=1;i<=n;i++)
    {
        int u;
        scanf("%d %d",&c[i],&u);
        if(c[i])//如果c[i]大于0,则一定是输入层
            q.push(i);
        else
            c[i]-=u;//否则对u进行预处理
    }
    for(int i=1;i<=p;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        ins(u,v,w);
        ind[v]++,oud[u]++;//对入度出度进行处理
    }
    topo();//记得排序
    bool flag=0;
    for(int i=1;i<=n;i++)
    {
        if(c[i]>0 && oud[i]==0)
        {
            printf("%d %d\n",i,c[i]);
            flag=1;
        }
    }
    if(!flag)
        printf("NULL\n");//不要忘输出NULL
    return 0;
}

反思

读题真的挺重要的,几乎掉的所有坑都是不仔细读题分析造成的

emm

图论。。。多练吧