| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
100*300的数据量我居然去开链表。。不清MLE,清就TLE,后来才反应过来要用邻接矩阵。。AC,顺便加了读入优化
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define c(a) memset(a,0,sizeof a)
short ans;
bool state[310];
short result[310];
short table[110][310];
short n1,n2,m;
void initialize(){c(table);ans=0;c(result);}
bool hungary(short x)
{
short i;
for(i=1;i<=n2;i++)if(table[x][i]&&!state[i])
{
state[i]=1;
if(!result[i]||hungary(result[i]))
{
result[i]=x;
return true;
}
}
return false;
}
inline void scan(short &x)
{
char c;
while(c=getchar(), c<'0'||c>'9');
x=c-'0';
while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0';
}
int main()
{
short T,i,j,y;
for(scan(T);T;T--)
{
initialize();
scan(n1);scan(n2);
for(i=1;i<=n1;i++)
{
scan(m);
for(j=1;j<=m;j++)scan(y),table[i][y]=1;
}
for(i=1;i<=n1;i++)
{
c(state);
if(hungary(i))ans++;
}
if(ans==n1)printf("YES\n");
else printf("NO\n");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator