OJ-Problems-Source/HDOJ/3517_autoAC.cpp

216 lines
4.9 KiB
C++
Raw Permalink Normal View History

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
#define maxn MAXN
const int MAXN = 508;
int G[MAXN][MAXN];
int mx[maxn],my[maxn];
int used[MAXN];
int ansX[maxn],ansY[maxn];
int delX,delY;
struct per
{
int dislike[maxn];
int like;
int dp;
};
per person[maxn];
int X[maxn],Y[maxn];
int nx,ny;
int shuchu[maxn];
int shuchu2[maxn];
#define clr(x) memset(x,0,sizeof(int)*MAXN)
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
int hungray(int m,int n,int mat[][maxn],int *match1,int *match2)
{
int s[maxn],t[maxn],p,q,ret=0,i,j,k;
for(_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
for(_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for(k=s[p],j=0;j<n&&match1[i]<0;j++)
if(mat[k][j]&&t[j]<0)
{
s[++q]=match2[j],t[j]=k;
if(s[q]<0)
for(p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
return ret;
}
bool Find(int v)
{
for(int u=0;u<ny;u++)
{
if(!used[u]&&G[v][u])
{
used[u]=1;
if(my[u]==-1||Find(my[u]))
{
mx[v]=u;my[u]=v; return 1;
}
}
}
return 0;
}
bool FindY(int v)
{
for(int u=0;u<ny;u++)
{
if(u!=delY&&!used[u]&&G[v][u])
{
used[u]=1;
if(my[u]==-1||FindY(my[u]))
{
return 1;
}
}
}
return 0;
}
bool FindX(int u)
{
for(int v=0;v<nx;v++)
{ if(v!=delX&&!used[v]&&G[v][u])
{
used[v]=1;
if(mx[v]==-1||FindX(mx[v]))
return 1;
}
}
return 0;
}
int MMG()
{
for(int i=0;i<nx;i++)mx[i]=-1;
for(int j=0;j<ny;j++)my[j]=-1;
int sum=0;
for(int i=0;i<nx;i++)
{
clr(used);
if(Find(i))
sum++;
}
return sum;
}
void Work()
{
printf("%d\n",nx+ny-MMG());
clr(ansX);
clr(ansY);
for(int i=0;i<nx;i++)
{ if(mx[i]==-1)
{
ansX[i]=1;
}
else
{
delY=mx[i];
clr(used);
if(FindY(i))ansY[delY]=1;
}
}
for(int j=0;j<ny;j++)
{
if(my[j]==-1)
ansY[j]=1;
else
{
delX=my[j];
clr(used);
if(FindX(j))ansX[delX]=1;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int a,b,p;
scanf("%d%d%d",&a,&b,&p);
memset(G,0,sizeof(G));
memset(person,0,sizeof(person));
clr(shuchu2);
clr(shuchu);
int like,num;
nx=0,ny=0;
for(int i=0;i<p;i++)
{
scanf("%d",&like);
if(like>a)
{
X[nx++]=i;
}
else
{
Y[ny++]=i;
}
person[i].like=like;
scanf("%d",&person[i].dp);
for(int j=0;j<person[i].dp;j++)
scanf("%d",&person[i].dislike[j]);
}
for(int i=0;i<nx;i++)
{
for(int j=0;j<ny;j++)
{
for(int t=0;t<person[Y[j]].dp;t++)
{
if(person[X[i]].like==person[Y[j]].dislike[t])
{
G[i][j]=1;break;
}
}
if(G[i][j]==0)
for(int t=0;t<person[X[i]].dp;t++)
{
if(person[Y[j]].like==person[X[i]].dislike[t])
{
G[i][j]=1;break;
}
}
}
}
Work();
int ipsc=0;
for(int t=0;t<nx;t++)
{
if(ansX[t]==1)
{
shuchu[ipsc++]=person[X[t]].like;
}
}
for(int t=0;t<ny;t++)
{
if(ansY[t]==1)
{
shuchu[ipsc++]=person[Y[t]].like;
}
}
sort(shuchu,shuchu+ipsc);
int ipsc2=0;
if(ipsc>0)
{
shuchu2[ipsc2++]=shuchu[0];
}
for(int t=1;t<ipsc;t++)
{
if(shuchu[t]!=shuchu[t-1])
{
shuchu2[ipsc2++]=shuchu[t];
}
}
printf("%d",ipsc2);
for(int t=0;t<ipsc2;t++)
{
printf(" %d",shuchu2[t]);
}
printf("\n");
}
return 0;
}