奖金

谁应该高谁的入度++,并记录下谁比低的高(低的得出度),所以入度为零的就是最低的(好不公平),找出所有最低的,将他们算作一层,奖金++(算是拓补排序吧)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n;
int r[9999];
int f[99][99];
int flag[999];
int m;
int a[99999];
int c[9999][999];
int main()
{
//freopen("reward.in","r",stdin);
//freopen("reward.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
c[b][++c[b][0]]=a;
r[a]++;
}
int nn=n;
int p=100;
int sum=0;
for(;nn>=1;)
{
int x=1;
int t=0;
while(x<=n)
{
if(r[x]==0)
{
sum+=p,r[x]=999999999,nn--,a[++t]=x;
}
x++;
}
if(t==0)
{
printf("Poor Xed");
return 0;
}
for(int j=1;j<=t;j++)
for(int i=1;i<=c[a[j]][0];i++)
{
r[c[a[j]][i]]--;
}
p++;

}
printf("%d",sum);
//fclose(stdin);
//fclose(stdout);
return 0;
}
最近的文章

烦人的幻灯片

将入度为一的区间(也就是唯一匹配的点和区间)找出来,把这个点所有出度的入度–,给这个点做标记,输出继续执行以上操作123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 …

于  拓补排序 继续阅读
更早的文章

团伙

反集的反集不是朋友。。。要是把他们合并便多了1234567891011121314151617181920212223242526272829303132333435363738//并查集+反集的思想 #include&lt;cstdio&gt;#include&lt;iostream&gt;usi …

于  并查集 反集 继续阅读