RE和MLE共存,这~~难道是人性的扭曲还是道德的沦丧~~。

回复帖子

@l_water 2018-09-14 23:05 回复

应该是我太蒟蒻了,求查查错误啊大佬们

#include<bits/stdc++.h>
using namespace std;
const int maxn=10e5+5;
int x[maxn],y[maxn],n,m,next[maxn],head[maxn],to[maxn],color[maxn],dfn[maxn],dp[maxn],low[maxn],s[maxn],t,tot,cnt,g,sum[maxn],f[maxn];
void add(int i,int j)
{
    next[++t]=head[i];
    to[t]=j;
    head[i]=t;
}
void tarjan(int now)
{
    dfn[now]=low[now]=++cnt,s[++tot]=now,f[now]=1;
    for(int i=head[now];i;i=next[i])
    {
        int y=to[i];
        if(!dfn[y])
        tarjan(y),low[now]=min(low[now],low[y]);
        else if(f[now])
        tarjan(y),low[now]=min(low[now],dfn[y]);
    }
    if(low[now]==dfn[now])
    {
        g++;
        while(s[tot+1]!=now)
        {
            color[s[tot]]=g;
            sum[g]=max(sum[g],s[tot]);
            f[s[tot--]]=false;
        }
    }
}
void dfs(int now)
{
    if(dp[now])
    return ;
    dp[now]=sum[now];
    for(int i=head[now];i;i=next[i])
    {
        int y=to[i];
        if(!dp[y])
        dfs(y);
        dp[now]=max(dp[now],dp[y]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)   
    {
        scanf("%d%d",&x[i],&y[i]);
        add(x[i],y[i]);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])
    tarjan(i);
    memset(head,0,sizeof(head));memset(next,0,sizeof(next));memset(to,0,sizeof(to));
    for(int i=1;i<=m;i++)
    if(color[x[i]]!=color[y[i]])
    add(color[x[i]],color[y[i]]);
    for(int i=1;i<=g;i++)
    if(!dp[i])
    dfs(i);
    for(int i=1;i<=n;i++)
    printf("%d ",dp[color[i]]);
    return 0;
}
@AC机的朋友AC鸭 2018-09-14 23:13 回复
#include<iostream>
#include<cstdio>
using namespace std;
int c,k,startx,starty;
int dt[401][401];
bool flag=0;
void move(int jd)
{
    for(int i=1;i<=c;i++)
    {
        for(int ii=1;ii<=k;ii++)
         {
            if (dt[i][ii]==jd-1)
             {
                if (dt[i-2][ii-1]==0&&i-2>=1) {dt[i-2][ii-1]=jd;flag=1;}
                if (dt[i+2][ii-1]==0&&i+2<=c) {dt[i+2][ii-1]=jd;flag=1;}
                if (dt[i-2][ii+1]==0&&i-2>=1) {dt[i-2][ii+1]=jd;flag=1;}
                if (dt[i+2][ii+1]==0&&i+2<=c) {dt[i+2][ii+1]=jd;flag=1;}
                if (dt[i-1][ii-2]==0&&ii-2>=1) {dt[i-1][ii-2]=jd;flag=1;}
                if (dt[i+1][ii-2]==0&&ii-2>=1) {dt[i+1][ii-2]=jd;flag=1;}
                if (dt[i-1][ii+2]==0&&ii+2<=k) {dt[i-1][ii+2]=jd;flag=1;} 
                if (dt[i+1][ii+2]==0&&ii+2<=k) {dt[i+1][ii+2]=jd;flag=1;} 
             }
         }
    }
    if (flag==0) return;
    else {flag=0;move(jd+1);}
}
int main()
{
cin>>c>>k>>startx>>starty;
dt[startx][starty]=1;
move(2);
for(int i=1;i<=c;i++)
{
    for(int ii=1;ii<=k;ii++)
     {
        if (dt[i][ii]!=0)  printf("%-5d", dt[i][ii]-1);
        else cout<<"-1   ";
     }
     cout<<endl;
}
} 

QAQ

@nothingness 2018-09-15 14:50 回复

@l_water

我就简单的拓扑过的

神奇乱搞算法(不过速度太慢了,100ms)

#include "bits/stdc++.h"
#define N 200001
using namespace std;

int n,m,t1,t2,p,f[N];
int k,b[N],first[N],next[N],last[N];
int q[N],h,t;

int add(int x,int y)
{
    k++;
    b[k]=y;
    if(first[x]==0)
        first[x]=k;
    else
        next[last[x]]=k;
    last[x]=k;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&t1,&t2);
        add(t2,t1);
    }
    for(int i=n;i>0;i--)
        if(!f[i])
        {
            h=t=0;
            q[++t]=i;
            f[i]=i;
            while(h<t)
            {
                p=first[q[++h]];
                while(p)
                {
                    if(f[q[h]]>f[b[p]])
                    {
                        f[b[p]]=f[q[h]];
                        q[++t]=b[p];
                    }
                    p=next[p];
                }
            }
        }
    for(int i=1;i<=n;i++)
        printf("%d ",f[i]);
    return 0;
}