QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#604828 | #8757. 图 | UESTC_DebugSimulator# | TL | 0ms | 0kb | C++17 | 1.5kb | 2024-10-02 14:06:57 | 2024-10-02 14:07:00 |
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 ...