P1983 求调
查看原帖
P1983 求调
559442
GWBailang楼主2023/10/13 17:14

样例一对的,样例二死循环,是因为 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
*/
2023/10/13 17:14
加载中...