801
poj 3687 Labeling Balls 逆向拓撲
要求輸出每個球的重量，標號越小的重量越輕越好。
逆向拓撲，從大向小查找入度為0的點，然後賦予最大的值，這樣就可以保證小號重量輕了
好久沒敲代碼了，完全不會敲了
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int n,m;
int map[201][201],in[201];
int ans[201];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(map,0,sizeof(map));
memset(in,0,sizeof(in));
scanf("%d%d",&n,&m);
int a,b,i;
for(i=0;i<m;i++)
{
scanf("%d%d",&b,&a);
if(map[a][b])continue;
map[a][b]=1;
in[b]++;
}
int Min=0,j,k=0;
bool flag=1;
for(i=n;i>=1;i--)
{
for(j=n;j>0,in[j]!=0;j--);
if(j==0){flag=0;break;}
for(int nn=1;nn<=n;nn++)
{
if(!map[j][nn])continue;
in[nn]--;
}
in[j]=i;
ans[i]=j;
}
if(!flag)printf("-1\n");
else
{
printf("%d",in[1]);
for(i=2;i<=n;i++)
printf(" %d",in[i]);
puts("");
}
}
}
最後更新：2017-04-04 07:03:36