1698.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#define null 0
const int size=1010;
int maxmatch(int n,int m,bool w[][size],int *p)

{

       int p_n[size];
      int p_m[size];
       bool sign[size];
       int q[size],from[size],s,t;
       int i,j,link,now,h;
       for(i=0;i<n;i++)p_n[i]=-1;
       for(j=0;j<m;j++)p_m[j]=-1
       for(i=0;i<n;i++)
       if(p_n[i]==-1)

       {

              for(j=0;j<m;j++)sign[j]=0;
              s=1;link=-1;
              from[0]=-1;
              q[0]=size-1;
              p_m[size-1]=i;
             for(t=0;t<s;t++)

              {
                     now=q[t];
                     for(j=0;j<m;j++)

                     {
                           if(w[p_m[now]][j]!=null&&sign[j]==0)

                            {
                                   sign[j]=1;
                                   q[s]=j;
                                   from[s++]=t;
                                  if(p_m[j]==-1)

                                   {

                                          link=s-1;
                                          break;

                                   }

                            }

                     }

                    if(j<m)break;

              }
              if(t<s)

              {
                     while(from[link]!=-1)

                     {
                            h=from[link];

                            p_m[q[link]]=p_m[q[h]];

                            

                            p_n[p_m[q[h]]]=q[link];

                            link=h;
                     }

              }
			else return 0;
       
       }
 //      int an;

  //     for(i=0,an=0;i<n;i++)
   //    {

     //         if(p)p[i]=p_n[i];

       //       if(p_n[i]>=0)an++;

       //}

       return 1;

}

//////////////////////////////////////////////////
bool w[size][size];

int main()
{
	int t,m,i,j,k,d,film,h;char day[7];
	cin>>t;
	while(t--)
	{
		cin>>film;
		for(i=0;i<film*50;i++)
		for(j=0;j<350;j++)
			w[i][j]=0;

		h=0;
		while(film--)
		{
			for(i=0;i<7;i++)cin>>day[i];
			cin>>d>>m;
			

			for(i=0;i<7;i++)
			if(day[i]=='1')
			{
				for(k=0;k<m;k++)
				for(j=h;j<h+d;j++)
					w[j][k*7+i]=1;
			}

			h+=d;

		}

		if(maxmatch(h,360,w,0))cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}