阅读801 返回首页    go 阿里云 go 技术社区[云栖]


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

  上一篇:go 【设计模式】【用DOM4J模拟spring实现简单工厂】
  下一篇:go 做一个饲养员给动物喂食物的例子体现JAVA中的面向对象思想,接口(抽象类)的用处