/*題目：假設有n門課程需要n個教師去授課，由于每個教師的專業特長不同，因此，要
        求每位教師只能承擔一門他所精通的課程的教學任務。
        請用圖結構設計，在n門課程編號、n個教師編號和他們各自專業特長都已知的
		情況下，輸出一張安排合理的教學任務表，支出每位教師要承擔什么課程。
        實現要求：
        ⑴  用二維數組S存儲所有教師的專業特長，其中：
        S[i][j]=0     表示i教師不精通j課程；S[i][j]=1     表示i教師精通j課程

        ⑵  用一維數組D存儲安排的教學任務表，其中：
        D[i]=0     表示i教師未安排課；D[i]=K(1≤k≤n)    表示i教師已安排課程k

        ⑶  課程門數n應由輸入隨機確定，且約定課程編號和教師編號均采用1，2…n，
		各位教師的專業特長也應由輸入隨機確定。
        ⑷  教學任務安排應以表格形式顯示。
---------------------------------------------------------------------
techer_speciality（教師專長課程設定）、主函數————————胡磊
edit（教師專長課程修改）,list(教師專長輸出),creat(初始化函數),sjcount(隨機生成老師專長) ——盧炯
serch、serch_error、anpai（課程安排） ———————————————鐘小玲
print_screen,pint_single,pint_segment,display（查看已經安排的教學任務）——————陳振鋒
cout_s,cout_t,print_list(按表格輸出教學任務)——————————謝賢穎

——————————————————————————————————*/

#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>//setw()
#include<time.h>
#define max 100
typedef struct {
        int s[max][max];//用二維數組存放教師專業特長
		int D[max];      //用一維數組存放安排的教學任務
}MGraph;
int c[max]={0};

///////////////初始化函數——盧炯//////////////////
int creat(MGraph &G,int *k,int &n,int b)         //初始化，將二維數組s和一維數組D的adj全部賦值為0
{
	int i,j;
	if(!b)
	{
		cout<<"請確定課程數或教師人數（1-"<<max-1<<"） ";cin>>n;

	    if (n<=0||n>max-1)  
		{cout<<"數字無效"<<endl;return (0);}
	    cout<<endl;
	    cout<<"科目數成功確定為  "<<n<<endl;
	}
	for(i=1;i<=n;i++)
	{	
		if(b==2)c[i]=0;
		else {
			G.D[i]=0;
            k[i]=0;
		    for(j=1;j<=n&&!b;j++)
		    G.s[i][j]=0;
		}
	}
	return(1);
	
}

/////////////教師專長課程設定——胡磊//////////////

int techer_speciality(MGraph &G, int n)
{
	
	int k;
	cout<<"請輸入教師專業特長編號(1-"<<n<<")  0表示結束輸入：\n";

	for(int i=1;i<=n;i++)
	{
		cout<<"輸入教師編號為 "<<i<<" 的特長專業號："<<endl;;
		do {
			cin>>k;
			if(k>n) {cout<<"超出范圍，重新輸入:   ";continue;}
			else G.s[i][k]=1;
		}while(k);
	}
	cout<<"設定成功！"<<endl;
	return (1);//設定成功！
}
//////////////搜索——鐘小玲////////////////

int serch(MGraph &G,int i,int j,int n)
{
	for(;j<=n;j++)
		if(G.s[i][j]==1)break;
		
		return(j);
}
//////////////課程安排——鐘小玲////////////////

int serch_error(MGraph &G,int *k,int n)//在已被進行安排過的老師都里運行
{
	int t;static int b=0;              //b檢測是否上一次沒被安排的課程也是同這位老師精通
	for(int j=1;j<=n;j++)
		if(k[j]==0)                    //存在有科目沒有老師授課
			for(int i=1;i<=n;i++)      //哪個老師可以授此科目且此科目當前還沒有老師授課
				if(G.s[i][j]==1)
				{	
					if(G.D[i]==0)return 0;   //此老師還沒受到安排，返回等此老師都有被進行安排過才進行
					if(b==i){k[G.D[i]]=-1;k[j]=i;G.D[i]=j;b=0;return 1;}else b=i;   //if(b!=i)b=i記錄第一個沒有授課的科目但有老師可以授課的老師下標
					                           //令這位老師只能選擇現在沒被安排的課程即k[j]=i，G.D[i]=j，
					                           //并令在再次搜索時即步驟①時，不再搜索上次沒被安排的課程即令k[G.D[i]]=-1		                          
					t=G.D[i];G.D[i]=j;k[j]=i;k[t]=0;return 1;  //有，讓此老師授此課，原來所授的課取消，重新安排過。
				}return 0;                     //(沒有科目沒有被安排)或者(有科目沒有被安排但沒有老師有此專長)
}
//——————————————————————//
void anpai(MGraph &G,int *k,int n)
{
	int j, js, p=1,t;
	for(int i=1;i<=n;i++)
		if(G.D[i]==0)
		{j=1;
		while(1)
		{
			js=serch(G,i,j,n);
			if(js<=n)
			{
				c[p++]=js;//保存從serch里返回的教師專長
				if(k[js]<=0)
				{
					G.D[i]=js;k[js]=i;p=1;creat(G,k,n,2);break;
				}
				else {j=js;j++;}
			}
			else {
				p=1;
				if(c[p]==0){ G.D[i]=0;break; }
				t=k[c[p]];
				j=c[p]+1;
				while(1)
				{
					js=serch(G,t,j,n);

					if(k[js]<=0&&js<=n)
					{
					    G.D[t]=js; k[js]=t; G.D[i]=c[p]; k[c[p]]=i; p=1; creat(G,k,n,2);break;
					}
					else if(js<=n)j++;
					else {
						p++;

						if(c[p]==0)
						{
							G.D[i]=0;creat(G,k,n,2); if(serch_error(G,k,n))anpai(G,k,n); break;
						}

					t=c[p];j=c[p]+1;
					}
				}//while
				break;
			}
		}//while
		}//if
}

/////////////////教師專長輸出——盧炯/////////////////
void list(MGraph &G,int n)
{
	int i,j,k;//k=0 記錄輸出個數
	for (i=1;i<=n;i++)
	{
		k=0;
		cout<<setw(3)<<i<<" 號教師的專業特長有: ";
		for(j=1;j<=n;j++)
			if (G.s[i][j]){
				k++;
				cout<<j<<setw(4); if((k%12)==0) {cout<<endl;cout<<setw(25);}
			}//打印15個換一行
			cout<<endl;
	}
	

}


//////////////教師專業修改——盧炯////////////////
void edit(MGraph &G, int n,int*k)        
{
   int s,i=0,m=0,j=0;
   cout<<"請輸入要修改的老師：";
   while(i==0||i>n){
                    cin>>i;
                   if(i>0&&i<=n)
                             cout<<"第"<<i<<"個老師的專長科目有: ";
                  else cout<<"沒這個老師！請重新輸入："<<endl;
                   }

   for(s=1;s<=n;s++)
 {
   if(G.s[i][s]==1)
  {
    cout<<s<<setw(3);
     j++;
  }
 }
   if(j==0)
   cout<<"沒有專長科目"<<endl;

   cout<<endl<<"輸入你要修改的科目(輸入0結束)："<<endl;

   do {
       cin>>s;
       if(s>n) {  cout<<"超出范圍，重新輸入:   ";continue; }
       else if(G.s[i][s]==1)
                       G.s[i][s]=0;
           else G.s[i][s]=1;
      }while(s);

   cout<<"修改后第"<<i<<"個老師的專長科目有 :";
   for(s=1;s<=n;s++)
 {
    if(G.s[i][s]==1)
   {
     cout<<s<<setw(3);
     m++;
   }
 }
   if(m==0)
      cout<<"沒有專長科目"<<endl;
   cout<<endl;
   creat(G,k,n,1);
}



///////////////隨機生成老師專長——盧炯////////////////////////////
void sjcount(MGraph &G, int n,int*k)//隨機生成老師專長
{
srand((unsigned int)time((time_t *)NULL));//srand() 來初始化偽隨機數發生器的種子，(當前時間)
for (int i=1;i<=n;i++){
	for (int s=1;s<=n;s++)
	{
          G.s[i][s]=rand() % 2;
	}
}
creat(G,k,n,1);//修改后把數組D和k全部賦值為0
}


//////////////謝賢穎//////////////////////
void cout_s(int s,int D[]) {//輸出科目編號 s , 當 D[s] 不足二位時前面輸出0
	cout<<"│";
	if(D[s]>9)cout<<D[s];
	else cout<<"0"<<D[s];
}

void cout_t(int k) {//輸出老師編號 k , 當 k 不足二位時前面輸出0
	cout<<"│";
	if(k>9)cout<<k;
	else cout<<"0"<<k;
}

void print_list(int D[],int f,int n) {//輸出數組D[f]至D[f+n-1]的所有元素

	int i,j,k,m,s;//m,s為開始位置,n為要輸出的記錄個數

	m=s=f;

	if(n>9) {//n>=10