http://acm.hdu.edu.cn/showproblem.php?pid=2647
题意:先给出人数n和关系数m,再给出工人之间的工资大小关系,例如给出a b表示a>b,求老板至少要给多少工资【注:工人至少有888元的工资】
Sample Input
2 1
1 2
2 2
1 2
2 1
6 5
2 4
3 6
3 5
1 2
1 3
4 3
1 2
3 4
2 3
Sample Output
1777
-1
5532
3558
#include <iostream>
#include <queue>
using namespace std;
#define M 10005
struct edge{
int v, w, nxt;
}e[20005];
int ind[M], p[M], cnt, money[M], n;
void init ()
{
cnt = 0;
memset (p, -1, sizeof(p));
memset (ind, 0, sizeof(ind));
for (int i = 1; i <= n; i++) money[i] = 888;
}
void addedge (int u, int v)
{
e[cnt].v = v, e[cnt].nxt = p[u], p[u] = cnt++;
}
int main()
{
int m, u, v, i, num, ans = 0;
while (~scanf ("%d%d", &n, &m))
{
init ();
while (m--)
{
scanf ("%d%d", &u, &v);
addedge (v, u); //逆向思维
ind[u]++;
}
queue<int> q;
for (i = 1; i <= n; i++)
if (ind[i] == 0)
q.push (i);
num = ans = 0;
while (!q.empty())
{
u = q.front();
q.pop();
ans += money[u]; //累加确定工资
num++;
for (i = p[u]; i != -1; i = e[i].nxt)
{
if (--ind[e[i].v] == 0)
{
money[e[i].v] = money[u] + 1;
q.push (e[i].v);
}
}
}
if (num < n) ans = -1;
printf ("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
hdu ACM 各种排序
最精准的答案(本人做对的题目拿上来给大家呈现)!不要忘记是C++编的
http://acm.hdu.edu.cn/showproblem.php?pid=2020 绝对值排序 txt格式
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
Hdu 1020解题报告,http://acm.hdu.edu.cn/showproblem.php?pid=1020
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu杭电所有题目按照ac数量排序,python分析
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
ACM HDU题目分类,我自己总结的大概只有十来个吧