Codeforces Round #652 (Div. 2) E. DeadLee 贪心

题意：

派会上有n种食物，每种食物有wi份。有m个朋友，每一个朋友有两种他喜欢吃的食物xi，yi。你需要判断他的朋友是否都能吃到食物。如果都能吃到食物，那么要输出朋友来的顺序，不能的话输出“DEAD”。

如果一个朋友来的时候发现两种他喜欢的食物都有，那么他会两种食物都吃一份，如果仅有一种食物还有，那么就只吃一份这种食物。

题解：

首先先预处理一下每一种食物有多少人要吃，我们设某种食物的需求量为needi份，如果某种食物的needi<=wi，那么只要喜欢第i种食物的人永远不可能没有食物吃。那么我们可以使用贪心策略，既然这些人什么时候都有吃的东西，那么我们就最后再通知他来派会，同时这些人对其他食物的需求我们可以消除掉，因为另一种食物有没有都不重要了。就一直这样判断看最后还有没有人没有加入到通知到派会，如果没有的话就输出“ALIVE”并输出序列

其次就是这道题的数据较大，所以暴力方法就不可行，我们就可以采用建图方式来解决问题，具体方法见代码

代码：

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<string>

 5 #include<queue>

 6 #include<string.h>

 7 #include<map>

 8 #include <iostream>

 9 #include <math.h>

10 using namespace std;

11 typedef long long ll;

12 #define maxn 300005

13 #include<vector>

14 struct node

15 {

16     int id,x;

17 };

18 vector<node>e[maxn];

19 queue<int>q;

20 int d[maxn],w[maxn],ans[maxn],vis[maxn];

21 int main()

22 {

23     int n,m;

24     scanf("%d %d",&n,&m);

25     for(int i=1;i<=n;i++)

26         scanf("%d",&w[i]);

27     for(int i=1;i<=m;i++)

28     {

29         int x,y;

30         scanf("%d %d",&x,&y);

31         e[x].push_back({i,y});

32         e[y].push_back({i,x});

33         d[x]++;d[y]++;

34     }

35     for(int i=1;i<=n;i++)

36     {

37         if(d[i]<=w[i])

38         {

39             q.push(i);

40         }

41     }

42     int f=m;

43     while(!q.empty())

44     {

45         int i=q.front();

46         q.pop();

47         //printf("i=%d\n",i);

48         for(int k=0;k<e[i].size();++k)

49         {

50             node j=e[i][k];

51             if(vis[j.id]==1)

52                 continue;

53             vis[j.id]=1;

54             d[j.x]--;

55             //printf("j.id=%d j.x=%d\n",j.id,j.x);

56             if(d[j.x]<=w[j.x]) q.push(j.x);

57             ans[f--]=j.id;

58

59         }

60     }

61     if(f)

62     {

63         printf("DEAD\n");

64         return 0;

65     }

66     printf("ALIVE\n");

67     for(int i=1;i<=m;i++)

68     {

69         printf("%d",ans[i]);

70         printf("%c",i==n?'\n':' ');

71     }

72 }

巴特西

Codeforces Round #652 (Div. 2) E. DeadLee 贪心

最新文章

热门文章