讨论 / 枚举轻松飘过。。。
囧TAT囧 2012-02-18 15:46:00
点我顶贴 收藏 删除
#include<stdio.h>//用枚举的思路,注意回溯

#include<stdlib.h>

int work[13][10];//第一维表示有12个工作,第二维前两个数据表示工作时间区间,以及3~10表示可以被哪些工人完成0

int worker[9][13][2];//表示这个工人的工作安排情况

int worktime[9];

int sign=0;

void diaodu(int n,int m);

int main()

{

int total,i,n,x,y,z,t,m,j;

scanf("%d",&total);

for(i=1;i<=total;i++)

{

scanf("%d",&n);

//初始化

for(x=0;x<13;x++)

for(y=0;y<10;y++)

work[x][y]=-1;

for(x=0;x<9;x++)

{

for(y=0;y<13;y++)

for(z=0;z<2;z++)

worker[x][y][z]=-1;

worktime[x]=0;

}

for(x=1;x<=n;x++)

{

scanf("%d%d",&work[x][0],&work[x][1]);//注意是2~9

scanf("%d",&m);

for(j=1;j<=m;j++)

{

scanf("%d",&t);

work[x][t+1]=1;

}

}

sign=0;//默认为不可调度

diaodu(n,1);//开始递归调度第一个工作

if(sign==0) printf("NO\n");

else printf("YES\n");

}

system("pause");

return 0;

}

void diaodu(int n,int m)

{

if(sign==0)

{

int i,j;//逐个遍历每一个工人

for(i=1;i<=8;i++)//i为工人编号

{

if(work[m][i+1]==1)//表示可以安排,要记得加1

{

for(j=1;j<=worktime[i];j++)//看工人工作时间是否冲突

{

if(work[m][0]>=worker[i][j][0]&&work[m][0]<=worker[i][j][1]) break;

if(work[m][0]<=worker[i][j][0]&&worker[i][j][0]<=work[m][1]) break;

}

if(j==worktime[i]+1)//表示不冲突,修改工人的工作属性

{

worktime[i]++;

worker[i][worktime[i]][0]=work[m][0];

worker[i][worktime[i]][1]=work[m][1];

if(n==m) sign=1;

else

{

diaodu(n,m+1);

worktime[i]--;

}

}

}

}

}

}

查看更多回复
提交回复