QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604828#8757. 图UESTC_DebugSimulator#TL 0ms0kbC++171.5kb2024-10-02 14:06:572024-10-02 14:07:00

Judging History

你现在查看的是最新测评结果

  • [2024-10-02 14:07:00]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-10-02 14:06:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int b[N],k[N];
int mtc[N][N],xz[N],no[N];
bool vis[N];
int nw[N];
vector<int>g[N];
bool dfs(int u){
	for(auto v:g[u]){
		if(vis[v])continue;
		vis[v]=1;
		for(int &ii=nw[v];ii<b[v];ii++){
			int i=ii;
			if(!mtc[v][i]||dfs(mtc[v][i])){
				mtc[v][i]=u;
				xz[u]=v;
				no[u]=i;
				return 1;
			}
		}
	}
	return 0;
}
void work(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>b[i];
		for(int j=0;j<b[i];j++)mtc[i][j]=0;
	}
	for(int i=1;i<=n;i++){
		cin>>k[i];
		g[i].clear();
		xz[i]=-1;
		for(int j=1;j<=k[i];j++){
			int x;
			cin>>x;
			g[i].push_back(x);
		}
	}
	memset(vis,0,sizeof(vis));
	memset(nw,0,sizeof(nw));
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!dfs(i))continue;
		ans++;
		memset(vis,0,sizeof(vis));
		memset(nw,0,sizeof(nw));
	}
	cout<<ans<<"\n";
	/*for(int i=1;i<=n;i++){
		cout<<xz[i]<<" "<<no[i]<<endl;
	}*/
	memset(vis,0,sizeof(vis));
	memset(nw,0,sizeof(nw));
	int cnt=0;
	while(cnt<ans){
		for(int i=1;i<=n;i++){
			if(xz[i]==-1||vis[i])continue;
			for(int j=0;j<k[i];j++){
				int p=g[i][j];
				if(p==xz[i]){
					if(nw[p]>=no[i]){
						cout<<i<<" ";
						nw[xz[i]]++;
						vis[i]=1;
						cnt++;
					}
					break;
				}
				if(nw[p]<b[p])break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i])cout<<i<<" ";
	}
	cout<<"\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)work();
	return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

10000
2 20
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 20
2 1
2 1
2 1
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 20
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 1
2 20
1 2
2 1
2 1
1 2
1 2
1 2
2 1
1 2
2 ...

output:


result: