首页 > 代码库 > 分银子
分银子
题目描述:
座山雕分银子给他们的兄弟们,发银子之前大伙发表意见。认为分给a的银子应该大于b。
输入:
n m(n个人,m个意见)
x y(认为x应该比y分的银子多)
m行
输出
最少分掉的银子。(最少分100两)
n<10000 m<20000
【思路】
拓扑排序
双队列很巧妙啊 我一开始怎么作都作不出来。ORZ
每一个人分的银子都是他前一个人的银子+1
我没有找到评测网站....
【code】
#include<iostream> #include<cstdio> #include<queue> using namespace std; int n,m,ans,r[100],cnt; vector<int>vec[100]; queue<int>q; queue<int>spt; void topsort() { for(int i=1;i<=n;i++) { if(!r[i]) { q.push(i); spt.push(100); } } while(!q.empty()) { int now=q.front();q.pop(); int c=spt.front();spt.pop(); ans+=c; cnt++; for(int i=0;i<vec[now].size();i++) { r[vec[now][i]]--; if(!r[vec[now][i]]) { q.push(vec[now][i]); spt.push(c+1); } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); vec[y].push_back(x); r[x]++; } topsort(); if(cnt!=n)printf("Unhappy!\n"); else printf("%d\n",ans); return 0; }
分银子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。