QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#604949 | #8759. 小班课 | UESTC_DECAYALI# | TL | 0ms | 3912kb | C++20 | 3.7kb | 2024-10-02 14:44:01 | 2024-10-02 14:44:01 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=505,INF=1e9;
int T,n,m,b[N],valid[N],mat[N]; vector <int> a[N];
namespace Network_Flow
{
const int NN=1005,MM=5e6+5;
struct edge
{
int to,nxt,v;
}e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t;
inline void addedge(CI x,CI y,CI z)
{
e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
}
#define to e[i].to
inline bool BFS(void)
{
memset(dep,0,(t+1)*sizeof(int)); dep[s]=1;
queue <int> q; q.push(s);
while (!q.empty())
{
int now=q.front(); q.pop();
for (RI i=head[now];i;i=e[i].nxt)
if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
}
return dep[t];
}
inline int DFS(CI now,CI tar,int dis)
{
if (now==tar) return dis; int ret=0;
for (RI& i=cur[now];i&&dis;i=e[i].nxt)
if (e[i].v&&dep[to]==dep[now]+1)
{
int dist=DFS(to,tar,min(dis,e[i].v));
if (!dist) dep[to]=INF;
dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
if (!dis) return ret;
}
if (!ret) dep[now]=INF; return ret;
}
#undef to
inline int Dinic(int ret=0)
{
while (BFS()) memcpy(cur,head,(t+1)*sizeof(int)),ret+=DFS(s,t,INF); return ret;
}
inline void build(void)
{
cnt=1; for (RI i=0;i<=t;++i) head[i]=0;
for (RI i=1;i<=n;++i) if (valid[i]) addedge(s,i,1);
for (RI i=1;i<=m;++i) if (b[i]>0) addedge(n+i,t,b[i]);
for (RI i=1;i<=n;++i)
for (RI j=0;j<a[i].size();++j) addedge(i,n+a[i][j],1);
// for (RI j=(int)a[i].size()-1;j>=0;--j) addedge(i,n+a[i][j],1);
}
};
using namespace Network_Flow;
int main()
{
//freopen("1.in","r",stdin);
for (scanf("%d",&T);T;--T)
{
scanf("%d%d",&n,&m); s=n+m+1; t=s+1;
for (RI i=1;i<=n;++i) valid[i]=1;
for (RI i=1;i<=m;++i) scanf("%d",&b[i]);
for (RI i=1;i<=n;++i)
{
int x; scanf("%d",&x); a[i].resize(x);
for (RI j=0;j<a[i].size();++j) scanf("%d",&a[i][j]);
reverse(a[i].begin(),a[i].end());
}
build(); int flow=Dinic();
printf("%d\n",flow);
for (RI i=1;i<=n;++i)
for (RI j=head[i];j;j=e[j].nxt)
if (1<=e[j].to-n&&e[j].to-n<=m&&e[j].v==0) mat[i]=e[j].to-n;
vector <int> ans;
while (ans.size()<flow)
{
for (RI i=1;i<=n;++i)
{
if (!valid[i]) continue;
if (mat[i]!=a[i].back()) continue;
// printf("fixed: %d\n",i);
ans.push_back(i); valid[i]=0;
if (!--b[mat[i]])
{
for (RI k=1;k<=n;++k)
if (!a[k].empty())
{
vector <int> tmp;
for (auto x:a[k])
if (x!=mat[i]) tmp.push_back(x);
a[k]=tmp;
}
}
}
// for (RI i=1;i<=n;++i)
// {
// printf("a[%d]: ",i);
// for (auto x:a[i]) printf("%d ",x); putchar('\n');
// }
// for (RI i=1;i<=m;++i) printf("b[%d]: %d\n",i,b[i]);
//printf("flow = %d\n",Dinic());
}
for (RI i=1;i<=n;++i) if (valid[i]) ans.push_back(i);
for (auto x:ans) printf("%d ",x); putchar('\n');
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3912kb
input:
3 5 5 1 1 1 1 1 4 1 3 2 4 1 5 4 3 4 2 1 2 3 5 1 1 5 3 1 2 2 2 1 2 2 1 2 2 1 3 2 1 3 2 1 3 5 5 1 1 1 1 1 2 1 2 2 5 4 2 3 2 2 4 3 2 5 1
output:
5 2 4 5 1 3 5 5 1 2 3 4 5 2 3 4 5 1
result:
ok Correct!
Test #2:
score: -100
Time Limit Exceeded
input:
250 2 1 2 1 1 1 1 1 1 1 0 2 2 1 1 1 1 2 2 1 2 2 0 2 2 1 2 1 2 1 1 1 1 1 1 2 1 0 0 1 2 1 0 0 2 1 2 1 1 0 1 2 1 0 0 2 1 2 1 1 1 1 1 1 1 1 1 1 2 1 0 1 2 2 2 2 0 1 1 1 2 1 1 1 0 1 1 1 0 1 2 0 1 1 1 2 2 1 1 1 1 2 1 2 2 2 1 1 2 2 1 2 2 1 1 2 0 1 1 2 2 1 2 1 1 0 2 2 2 0 1 1 1 2 1 1 1 1 1 2 1 2 0 1 1 1 1 1 ...