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 <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define Max 10011
int n, ind[Max], v[Max];
struct node{
int son;
node *next;
}*N[Max];
void init ()
{
for (int i = 1; i <= n; i++)
v[i] = 888, ind[i] = 0, N[i] = NULL;
}
void insert (int a, int b) //b作为a的儿子
{
node *p = new node;
p->son = b;
p->next = N[a];
N[a] = p;
}
int main()
{
int m, i, a, b, num, res;
while (~scanf ("%d%d", &n, &m))
{
num = n;
init(); //初始化
while (m--)
{
scanf ("%d%d", &a, &b);
insert (b, a);
//逆向思维的突破，本来是大的做老爸，现在是反了，大的是儿子，方便处理
ind[a]++;
}
queue<int> q;
for (i = 1; i <= n; i++)
if (ind[i] == 0)
q.push (i);
while (!q.empty())
{
num--;
int t = q.front();
q.pop();
for (node *p = N[t]; p; p = p->next) //根据入度层层遍历，灰常有层次
{
v[p->son] = v[t] + 1; //根据题意，儿子的钱=老爸的钱+1
if (--ind[p->son] == 0)
q.push (p->son);
}
}
if (num > 0) //关键计数器
{
puts ("-1");
continue;
}
res = 0;
for (i = 1; i <= n; i++) //老板至少要给所有工人的总工资
res += v[i];
printf ("%d\n", res);
}
return 0;
}
相关文章
