QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#604916#8759. 小班课UESTC_DECAYALI#TL 1ms4096kbC++204.0kb2024-10-02 14:33:342024-10-02 14:33:34

Judging History

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

  • [2024-10-02 14:33:34]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4096kb
  • [2024-10-02 14:33:34]
  • 提交

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]; 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("H.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);
        vector <int> ans;
        while (ans.size()<flow)
        {
            for (RI i=1;i<=n;++i)
            {
                if (!valid[i]) continue;
                // 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) printf("i = %d ; match = %d; tar = %d\n",i,e[j].to-n,a[i].back());
                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)
                {
                    if (e[j].to-n!=a[i].back()) continue;
                    // printf("fixed: %d\n",i);
                    ans.push_back(i); valid[i]=0;
                    if (!--b[e[j].to-n])
                    {
                        for (RI k=1;k<=n;++k)
                        if (!a[k].empty())
                        {
                            vector <int> tmp;
                            for (auto x:a[k])
                            if (x!=e[j].to-n) tmp.push_back(x);
                            a[k]=tmp;
                        }
                    }
                    break;
                }
            }
            // 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]);
            build(); Dinic(); //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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4096kb

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
...

output:


result: