Reward(拓扑排序)
Reward(拓扑排序)
1944864971 发表于2年前
Reward(拓扑排序)
  • 发表于 2年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

http://acm.hdu.edu.cn/showproblem.php?pid=2647
题意:
老板要给n个员工发工资最低工资是888;
但是工人们是有要求的 如果输入 a b 表示a的工资要比b的工资高
求出老板最少准备多少工资

include

include

include

include

include

/**
1:拓扑排序(数据结构书上有)

    用一个队列来储存入度为零的点
    开始遍历这些点 遍历之后把以这个点开头的边删除比如a到b 遍历a时把b的度减一
2: 邻接表储存(用vector容器来实现邻接表的储存较为简单)

*/

using namespace std;
struct node
{
int b;
};
vector edge[10005];
int du[10005];
int value[10005];
void creatLinJieBiao(int a,int b)///创建邻接表
{
node t;
t.b=b;
edge[a].push_back(t);///已a开头b结尾的边
du[b]++;///顶点b的入度加一
}
bool topSort(int n)///拓扑排序
{
queue q;
for(int i=1; i<=n; i++)
if(du[i]==0)q.push(i);
int count=0;
while(!q.empty())
{
int a=q.front();
count++;
q.pop();
for(int i=0; i<edge[a].size(); i++)
{
du[edge[a][i].b]--;
if(du[edge[a][i].b]==0)
{
value[edge[a][i].b]= value[a]+1;///b的只要比a的值高
q.push(edge[a][i].b);
}
}
}
if(count!=n)return false;///如果最后仍有某个点的度不为0那么即是存在环
return true;
}

int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(value,0,sizeof(value));
memset(du,0,sizeof(du));
memset(edge,0,sizeof(edge));
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
creatLinJieBiao(b,a);///要求a比b的值大
}
int sum=0;
if(topSort(n))
{
for(int i=1; i<=n; i++)
{
sum+=888+value[i];
}

        printf("%d\n",sum);
    }
    else
        printf("-1\n");
}
return 0;

}

/**
5 4
1 2
2 3
3 4
5 3

5 6
1 2
2 3
3 4
4 5
1 5

*/

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: