Problem 1041 - 女儿岛游记
题目描述：
Description
话说，一日，Qinz大牛游荡到了一个岛上，惊喜地发现这岛就是传说中的“女儿岛”，岛上美女如云，Qinz每日与众美女游山玩水，不亦乐乎。直到有一天，Qinz发现自己的胡子不但不长了反而往下掉，而且体型也发生了变化……Qinz要变成女人了！悲痛之时，女儿岛的岛主—女帝给了Qinz一些药水和一本宝典，并告诉“她”，只要按宝典规定的顺序服下药水就能恢复男儿身。宝典上规定了某些药必须在服用了另一些药的前提下才可服用，不然将产生可怕的反作用（比如变成双性人）。不幸的是，由于年代久远，宝典上的一些字已经模糊不清了，然而服药的顺序只可能有一种。请问Qinz能够根据已知的关系找出这唯一的服药顺序，从而顺利地变回纯爷们吗？（提示：宝典上的条目可能会重复，药水的关系不会形成环）
Input
输入的第一行包含一个整数T，表示有T组数据。
每组数据的第一行包含两个整数N（2≤N≤50），M（0≤M≤60）。分别表示药水的数量和宝典上能够看清的条目数。
接下来的M行，每行两个整数 A B。表示必须服用药水编号为A的药水后才能服用编号为B的药水，药水编号从1到N。
Output
每组数据输出一行，如果Qinz能够确定这唯一的服用顺序，输出该顺序，否则输出-1。
Sample Input
3
2 1
1 2
3 3
3 1
2 1
2 3
4 2
1 2
3 4
Sample Output
1 2
2 3 1
-1
分析过程：
这个题我用了两种方法，第一种方法：建表，采用了类似Pro1037智破机枪阵的方法，用匈牙利算法求出结果，如果最终生成的最大链长度不是N，就输出-1。
代码：
程序代码：
第二种方法：
见一个数组，list[i]表示i元素应该在第几个出现。不停的刷list的数据，直到不再变化为止。算法复杂度应该是O（N3）吧，但是因为数据量小，所以能过。
如果药典给的提示不够的话，那么list中必然有两个或以上的相同元素，此时也必缺少某个位置应该出现的元素，输出-1
代码：
程序代码：
题目描述：
Description
话说，一日，Qinz大牛游荡到了一个岛上，惊喜地发现这岛就是传说中的“女儿岛”，岛上美女如云，Qinz每日与众美女游山玩水，不亦乐乎。直到有一天，Qinz发现自己的胡子不但不长了反而往下掉，而且体型也发生了变化……Qinz要变成女人了！悲痛之时，女儿岛的岛主—女帝给了Qinz一些药水和一本宝典，并告诉“她”，只要按宝典规定的顺序服下药水就能恢复男儿身。宝典上规定了某些药必须在服用了另一些药的前提下才可服用，不然将产生可怕的反作用（比如变成双性人）。不幸的是，由于年代久远，宝典上的一些字已经模糊不清了，然而服药的顺序只可能有一种。请问Qinz能够根据已知的关系找出这唯一的服药顺序，从而顺利地变回纯爷们吗？（提示：宝典上的条目可能会重复，药水的关系不会形成环）
Input
输入的第一行包含一个整数T，表示有T组数据。
每组数据的第一行包含两个整数N（2≤N≤50），M（0≤M≤60）。分别表示药水的数量和宝典上能够看清的条目数。
接下来的M行，每行两个整数 A B。表示必须服用药水编号为A的药水后才能服用编号为B的药水，药水编号从1到N。
Output
每组数据输出一行，如果Qinz能够确定这唯一的服用顺序，输出该顺序，否则输出-1。
Sample Input
3
2 1
1 2
3 3
3 1
2 1
2 3
4 2
1 2
3 4
Sample Output
1 2
2 3 1
-1
分析过程：
这个题我用了两种方法，第一种方法：建表，采用了类似Pro1037智破机枪阵的方法，用匈牙利算法求出结果，如果最终生成的最大链长度不是N，就输出-1。
代码：
程序代码：
#include <stdio.h>
#include <string.h>
int N,M;
unsigned char map[64][64];
unsigned char exist[64],after[64];
int find(int x)
{
int i;
for(i=1;i<=N;i++)
{
if( map[i][x] && !exist[i]) {
exist[i]=1;
if(after[i]==0 || find(after[i])) {
after[i]=x;
return 1;
}
}
}
return 0;
}
int main(int argc, char *argv[])
{
int T;scanf("%d",&T);
while(T--)
{
int a,b,i,firstOne=0;
memset(map,0,sizeof(map));
memset(after,0,sizeof(after));
scanf("%d%d",&N,&M);
for(i=0;i<M;i++) {
scanf("%d%d",&a,&b);
map[a][b]=1;
}
for(i=1;i<=N;i++)
{
memset(exist,0,sizeof(exist));
if(!find(i)) {
if(firstOne==0) firstOne=i;
else {
printf("-1");
break;
}
}
}
if(i>N){
int x=firstOne;
for(i=1;i<=N;i++)
printf("%d ",x),x = after[x];
}
printf("\n");
}
return 0;
}
第二种方法：
见一个数组，list[i]表示i元素应该在第几个出现。不停的刷list的数据，直到不再变化为止。算法复杂度应该是O（N3）吧，但是因为数据量小，所以能过。
如果药典给的提示不够的话，那么list中必然有两个或以上的相同元素，此时也必缺少某个位置应该出现的元素，输出-1
代码：
程序代码：
#include <iostream>
#include <string.h>
int N,M;
int d[64][2];
int list[64];
int ansLst[64];
using namespace std;
bool cal()
{
bool ans=true;
for(int i=0;i<M;i++)
{
if(list[d[i][0]]>=list[d[i][1]])
{
list[d[i][1]]=list[d[i][0]]+1;
ans = false;
}
}
return ans;
}
bool mkAns()
{
for(int i=0;i<N;i++)
{
int j=1;
for(j=1;j<=N;j++)
{
if(list[j] == i) {
ansLst[i]=j;
break;
}
}
if(j>N) return false;
}
return true;
}
int main(int argc, char *argv[])
{
int T;cin>>T;
while(T--)
{
memset(d,0,sizeof(d));
memset(ansLst,0,sizeof(ansLst));
memset(list,0,sizeof(list));
cin>>N>>M;
for (int i=0; i<M; i++)
{
cin>>d[i][0]>>d[i][1];
}
while(!cal());
if(mkAns()){
for (int i=0; i<N; i++) cout<<ansLst[i]<<' ';
cout<<endl;
}else cout<<"-1"<<endl;
}
}
