Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

100*300的数据量我居然去开链表。。不清MLE,清就TLE,后来才反应过来要用邻接矩阵。。

Posted by PoPoQQQ at 2014-05-22 18:27:45 on Problem 1469
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator