Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1072????Accepted Submission(s): 318
?
Sample Input2 1 1 2 2 2 1 2 2 1
?
Sample Output1777 -1?
?????? 最经典的拓扑排序,题目大意:给你a和b,则a的功劳大于b的功劳,即a所得的报酬比要b的多,先输入n和m,表示有n个人,m种关系。报酬至少是888元,问你要分配这些报酬,至少要给多少钱?如果这些关系出现问题(出现环),输出-1。
??????? 就是一个拓扑排序,不解释了,直接代码吧。
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2647
代码:
?#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
const int N = 10005;
const int M = 20005;
struct edge
{
int w;
edge *next;
}*e[N];
edge memory[M];
int cnt;
int deg[N], money[N];
int n, m;
void init() //初始化
{
cnt = 0;
for(int i = 0; i <= n; i++)
{
e[i] = NULL;
money[i] = 888;
deg[i] = 0;
}
}
void add(int x, int y) //建边
{
edge *p = &memory[cnt++];
p->w = y;
p->next = e[x];
e[x] = p;
}
int main()
{
int i, x, y, k, u, num, sum;
while(scanf("%d %d", &n, &m) != EOF)
{
init();
sum = 0;
num = n;
for(i = 1; i <= m; i++)
{
scanf("%d %d", &x, &y);
add(y, x); //建边
deg[x]++; //度数++
}
/// 拓扑排序
queue<int> Q;
for(i = 1; i <= n; i++)
{
if(deg[i] == 0) Q.push(i);
}
while(!Q.empty())
{
k = Q.front();
Q.pop();
num--;
for(edge *p = e[k]; p; p = p->next) //链表代替矩阵
{
u = p->w;
if(--deg[u] == 0) //和k连接的点度数--,若为0,入队列
{
money[u] = money[k] + 1; //钱比连接点k的钱多1
Q.push(u);
}
}
}
if(num > 1) printf("-1\n"); //入队列次数少于n,证明有环
else
{
for(i = 1; i <= n; i++)
{
sum += money[i];
}
printf("%d\n", sum);
}
}
return 0;
}
?
?
?