作者：hro5028136 | 来源：互联网 | 2024-11-09 15:43
题目E.DeadLee：思维导图与拓扑结构的深度解析问题描述：给定n种食物，每种食物的数量由wi表示。同时，有m位朋友，每位朋友喜欢两种特定的食物x和y。目标是通过合理分配食物，使尽可能多的朋友感到满意。本文将通过思维导图和拓扑排序的方法，对这一问题进行深入分析和求解。
题：https://codeforces.com/contest/1369/problem/E
题意：有n种食物，wi 表示第 i 种食物的个数，m个朋友，喜欢俩种食物x和y（x，y<=n），确定朋友吃食物的顺序，每次要是还有喜欢的食物就会吃一个（要是x和y都有则都吃x和y），让每个朋友都能吃到至少一个喜欢的食物
分析：很容易想到，要是需求小于等于 wi ，则第 i 种食物即使全部想要吃它的朋友都有吃到它那也是成立的 ，就不存在分配排序问题。那么我们可以安排这部分到最后，因为前面人即使把其他吃完也能保证能吃到第 i 种食物。
为了方便处理，我们把x和y处理成无向图的边，需求就是度数d，而处理，虽然要把di<=wi的放在后面，我们可以先处理这部分，最后答案翻转即可，而核心部分的贪心就类似拓扑图去处理，每次选择合法部分（di<=wi）将连着 i 的度数-1。
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int M=2e5+5;
#define pb push_back
#define MP make_pair
int w[M],du[M],book[M];
vectorint,int> >g[M];
vector<int>ans;
queue<int>que;
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int x,y,i=1;i<=m;i++){
scanf("%d%d",&x,&y);
g[x].pb(MP(y,i));
g[y].pb(MP(x,i));
du[x]++,du[y]++;
}
for(int i=1;i<=n;i++)
if(du[i]<=w[i])
que.push(i);
while(!que.empty()){
int now=que.front();
que.pop();
for(auto it:g[now]){
int v=it.first,id=it.second;
if(book[id])
continue;
book[id]=1;
ans.pb(id);
if(--du[v]==w[v])
que.push(v);
}
}
if(ans.size()<m)
return puts("DEAD"),0;
puts("ALIVE");
reverse(ans.begin(),ans.end());
for(auto it:ans)
printf("%d ",it);
return 0;
}
E. DeadLee（思维，拓扑图处理）
京公网安备 11010802041100号