| ||||||||||
| 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 | |||||||||
RPWT ^_^In Reply To:why wa? Posted by:star6 at 2007-08-14 21:17:01 > #include<cstdio>
> #include<algorithm>
>
>
> const int maxn=301;
>
> struct mnode
> {
> int v;
> mnode *next;
> };
>
> mnode mem[maxn];
> int mtail;
>
> mnode *graph[maxn];
> int n,m;
>
> int matchy[maxn];
> bool marked[maxn];
>
> void gadd(int u,int v)
> {
> mtail++;
> mem[mtail].v=v;
> mem[mtail].next=graph[u];
> graph[u]=&mem[mtail];
> }
> void init()
> {
> int i,t,v;
>
> mtail=0;
> memset(graph,0,sizeof(graph));
> scanf("%d %d\n",&n,&m);
> memset(matchy,0,sizeof(matchy));
> memset(marked,0,sizeof(marked));
>
> for (i=1;i<=n;i++)
> {
> scanf("%d",&t);
> while (t--)
> {
> scanf("%d",&v);
> gadd(i,v);
> }
> scanf("\n");
> }
>
> }
>
> bool search(int v)
> {
> mnode *iter;
>
> if (marked[v])
> return(false);
>
> marked[v]=true;
> for (iter=graph[v];iter;iter=iter->next)
> if ((!matchy[iter->v])||(search(matchy[iter->v])))
> {
> matchy[iter->v]=v;
> return(true);
> }
> return(false);
> }
> void starmain()
> {
> int i;
>
> for (i=1;i<=n;i++)
> {
> memset(marked,0,sizeof(marked));
> if (!search(i))
> {
> printf("NO\n");
> return;
> }
> }
> printf("YES\n");
>
> }
> int main()
> {
> int t;
>
> // freopen("c:\\in.txt","r",stdin);
>
> scanf("%d\n",&t);
> while (t--)
> {
> init();
> starmain();
> }
> return(0);
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator