#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 11003

int Visit[MAX_N];
int Storage[MAX_N];

int N = 0, K = 0, iWholeNum = 0;
initVariable()
{
		int i = 0;
		for(i=0; i<MAX_N; i++)
		{
				Visit[i]=0;
				Storage[i]=0;
		}
}

printfTest()
{
		int i = 0;
		printf("the storage \n");
		for(i = 0; i<=N; i++)
		{
				printf("the i is %d, Storage[i] is %d\n", i, Storage[i]);
		}

		printf("the visit \n");
		for(i = 0; i<=N; i++)
		{
				printf("the i is %d, Visit[i] is %d\n", i, Visit[i]);
		}
}


int main()
{
		int i = 0, j = 0, k = 0;
		int iVacumm = 0;
		int iMove = 0;
		int iTemp = 0,iLast = 0,  iCycle = 0;
		int iFileSn = 0;

		initVariable();
		scanf("%d %d",&N, &K);
		for(i = 0; i<K; i++)
		{
				scanf("%d", &iFileSn);
//				printf("i is %d, iFileSn is %d\n", i, iFileSn);
				for(j = 0; j<iFileSn; j++)
				{
						iWholeNum++;
						scanf("%d", &Storage[iWholeNum]);
						Visit[Storage[iWholeNum]] = iWholeNum;
//						printf("j is %d, Storage[iWholeNum] %d, Visit[[Storage[iWholeNum]]] is %d\n", j, Storage[iWholeNum], Visit[Storage[iWholeNum]]);

				}
		}
		//for(i = 0; i<=N; i++)
		//{
		//		printf("the i is %d, Visit[i] is %d\n", i, Visit[i]);
		//}

		for(i = N; i>=1; i--)
		{
				if( 0 == Visit[i])
				{
						iVacumm = i;
						break;
				}
		}
//		printf("the iVacumm is %d\n", iVacumm);

		for(i = 1; i<=iWholeNum; i++)
		{
				if(i != Storage[i])
				{
						if(0 == iMove)
								iMove = 1;

//						printf("i is %d, Visit[i] is %d\n", i, Visit[i]);
						if(0 == Visit[i])
						{

								printf("%d %d\n", Storage[i], i );
								Visit[Storage[i]] = 0;
								Visit[i] = i;
								Storage[i] = i;
						}else 
						{
								iTemp = i;

								while(Visit[iTemp])
								{
						//				printf("iTemp %d, Visit[iTemp] is %d\n", iTemp, Visit[iTemp]);
										iTemp = Visit[iTemp];
										if(i == Visit[iTemp])
										{
										//		printf("the Cycle \n");
												iCycle = 1;
												break;
										}

								}
								iLast = iTemp;
						
						//		printf("the final iTemp is %d, Storage[iTemp] is %d, iCycle is %d, iLast is %d\n",iTemp, Storage[iTemp], iCycle, iLast);
								if (1==iCycle)
								{
										//printf("Cycle\n");
										printf("%d %d\n", iTemp, iVacumm);
										Visit[iTemp] = 0;
										iTemp = Storage[iTemp];
										while(1)
										{
												printf("%d %d\n",iTemp, Visit[iTemp]);
												Visit[Visit[iTemp]] = Visit[iTemp];
												Storage[Visit[iTemp]] = Visit[iTemp];
												iTemp = Storage[iTemp];
											//	printf("puzzle iTemp is %d, Visit[iTemp] is %d\n", iTemp, Visit[iTemp]);
												if(iLast == iTemp)
														break;

										}
										printf("%d %d\n", iVacumm, i);
										Visit[i] = i;
										Storage[i] = i;
										iCycle = 0;

						
								}
								else
								{

								//		printf("link\n");
										iTemp = Storage[iTemp];
										while(1)
										{
												printf("%d %d\n", iTemp, Visit[iTemp]);
												Visit[Visit[iTemp]] = Visit[iTemp];
												Storage[Visit[iTemp]] = Visit[iTemp];
												if(iTemp == i)
														break;

												iTemp = Storage[iTemp];
										}

										printf("%d %d\n", Storage[i], i);

										Visit[Storage[i]] = 0;
										iVacumm = Storage[i];
										Visit[i] = i;
										Storage[i] = i;

										iCycle = 0;
								}
								
						}


				}
		}
		if(0 == iMove)
				printf("No optimization needed\n");

//		printfTest();


		return 0;
}

• Re:求大神指点。discuss里的测试数据全部过了。咋还是WA。。。 (4046) 274856653 2018-11-18 11:07:07
  • Re:求大神指点。discuss里的测试数据全部过了。咋还是WA。。。 (17) 274856653 2018-11-18 11:07:40
    • Re:求大神指点。discuss里的测试数据全部过了。咋还是WA。。。 (116) 274856653 2018-11-19 09:05:06