求助,加虚拟点拓扑排序的方法思路是怎么样的
查看原帖
求助,加虚拟点拓扑排序的方法思路是怎么样的
490694
Compound_Interest楼主2022/3/14 16:51
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2e3+10;
int a[maxn],n,m,b[maxn],cnt,in[maxn],num,G[maxn][maxn],ans;
bool book[maxn],vis[maxn];
int main(){
	scanf("%d%d",&n,&m);
	int tmp;
	for(int i=1;i<=m;i++){
		memset(book,0,sizeof(book));
		scanf("%d",&tmp);
		for(int j=1;j<=tmp;j++){
			scanf("%d",&a[j]);book[a[j]]=1;
		}
		for(int j=a[1];j<=a[tmp];j++)
			if(!book[j]){
				G[j][n+i]=1,in[n+i]++;
		//		printf("%d->%d\n",j,n+i);
			}
		for(int j=1;j<=tmp;j++){
			G[n+i][a[j]]=1,in[a[j]]++;
		//	printf("%d->%d\n",n+i,a[j]);
		}
	}
/*	for(int i=1;i<=n+m;i++)
		for(int j=1;j<=n+m;j++)
			if(G[i][j]) printf("%d->%d\n",i,j);*/
	while(1){
		bool flag=1;
		cnt=0;
		for(int i=1;i<=n+m;i++) if(!in[i]&&!vis[i]){
			b[++cnt]=i,vis[i]=1;
			if(i>n) flag=0;
		}
		//for(int i=1;i<=cnt;i++) printf("b[%d]=%d\n",i,b[i]);1
		if(!cnt) break;
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=n+m;j++)
				if(G[b[i]][j]&&!vis[j]){
					in[j]--;
				//	printf("in[%d]=%d\n",j,in[j]);
				}		
		ans+=flag;
	}
	printf("%d",ans);
	return 0;
}

此做法90分,应该是忽略了虚拟点和真实点在同一层的情况,求调

2022/3/14 16:51
加载中...