P1983 求调

P1983 [NOIP2013 普及组] 车站分级

GWBailang @ 2023-10-13 17:14:49

样例一对的,样例二死循环,是因为 dian 没有变成 0 所以死循环。所以为啥 dian 最后没有变成 0。

#include<bits/stdc++.h>
using namespace std;
vector<int>jl[1005];
struct Node{
    int v,nxt;
}bian[1000005];
int head[1005];
int rd[1005];
int bnt;
int dian;
bool sf[1005];
void add(int u,int v){
    bian[++bnt]={v,head[u]};
    head[u]=bnt;
    rd[v]++;
}
int main(){
    //  freopen("A/in.in","r",stdin);
    //  freopen("A/out.out","w",stdout);
    int n,m,x,q,y,z;
    cin>>n>>m;
    dian=n;
    for(int i=1;i<=m;i++){
        cin>>x>>q;
        y=q;
        x--;
        while(x--){
            cin>>z;
            for(int i=y+1;i<z;i++)
                add(i,q);
            add(q,z);
            y=z;
        }
    }
    int cnt=0;
    while(dian){
        cnt++;
        for(int i=1;i<=n;i++){
            if(!sf[i]&&rd[i]<=0){
                dian--;
                sf[i]=true;
                for(int j=head[i];j;j=bian[j].nxt){
                    if(!sf[bian[j].v])rd[bian[j].v]--;
//                  cout<<1<<" ";
//                  cout<<bian[j].v<<endl;
//                  cout<<1<<endl;
                }
            }
        }
        for(int i=1;i<=n;i++)cout<<rd[i]<<" "<<sf[i]<<" ";
        cout<<"--\n";//调试信息
    }
    cout<<cnt<<endl;
    return 0;
}
/*调试信息循环输出:
  2 0 
  0 1
  1 0
  0 1
  3 0
  2 0
  0 1
  0 1
  1 0
*/

by GWBailang @ 2023-10-13 17:15:30

哦对提交30分,3个AC,剩下的都TLE,应该就都是死循环了


by GWBL @ 2023-10-13 19:27:15

@GWBailang 首先,数据可达 10^6,建议你使用scanf进行输入


by GWBailang @ 2023-10-13 19:33:22

@GWBailang_XHao 其次?


by GWBL @ 2023-10-13 19:35:35

而且样例2里sf和rd和dian一直都没变


by GWBL @ 2023-10-13 19:36:36

@GWBailang 等会儿你这代码我还没太看懂


by GWBL @ 2023-10-13 19:39:01

@GWBailang 也就说明……一直没进39行的if


by GWBL @ 2023-10-13 19:40:32

@GWBailang 也就进一步说明rd[i]一直大于零


by GWBL @ 2023-10-13 19:41:44

@GWBailang 所以我觉得问题大概出在前面输入和add的部分


by GWBailang @ 2023-10-13 19:41:57

……


by GWBL @ 2023-10-13 19:43:07

@GWBailang 或者就是if的条件写错了


| 下一页