计蒜客 | 拓扑排序 | 虎威山上的分配
2018-06-17 21:37:43来源:未知 阅读 ()
每年过年的时候,座山雕都会给兄弟们分银子,分银子之前,座山雕允许大伙儿发表意见,因为要是没法满足所有人的意见,指不定谁要搞出什么大新闻。不过每个人在提意见的时候只能说:“我认为 A 分的银子应该比 B 多!”。座山雕决定要找出一种分配方案,满足所有人的意见,同时使得所有人分得的银子总数最少,并且每个人分得的银子最少为 100 两。
输入格式
第一行两个整数 n,m(0<n≤10000,0<m≤20000),表示总人数和总意见数;
以下 m 行,每行两个整数 a,b,之间用一个空格隔开,表示某个意见认为第 a 号小弟所分得的银两应该比第 b号小弟多,所有小弟的编号由 1开始。
输出格式
若无法找到合法方案,则输出Unhappy!
(不包含引号),否则输出一个数表示最少总银两数。
样例输入
3 2 1 2 2 3
样例输出
303
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int max_num = 100005; 4 /* 5 ip:第几条边 6 indeg:表示入度 7 seg: 8 */ 9 int head[max_num],ip,indegree[max_num]; 10 int n,m,seq[max_num]; 11 12 struct note{ 13 int v,next; 14 }edge[max_num]; 15 16 void init() 17 { 18 memset(head,-1,sizeof(head)); 19 memset(indegree,0,sizeof(indegree)); 20 ip = 0; 21 } 22 23 void addedge(int u,int v) //增加边,u是起点,V是终点 24 { 25 edge[ip].v = v,edge[ip].next = head[u],head[u] = ip++; 26 } 27 28 int topo() 29 { 30 int ans = 0; 31 queue<int>q; 32 queue<int>money; //模板的基础上添加一个存储银子的队列 33 int indeg[max_num]; 34 for(int i = 1; i <= n; i++) 35 { 36 indeg[i] = indegree[i]; 37 if(indeg[i] == 0) 38 { 39 q.push(i); 40 money.push(100); //对于入度为0的人,基础银子为100 41 } 42 43 44 } 45 int k = 0; 46 bool res = false; 47 while(!q.empty()) 48 { 49 if(q.size() != 1) 50 res = true; 51 int u = q.front(); 52 int temp = money.front(); 53 ans += temp; 54 q.pop(); 55 money.pop(); 56 k++; 57 for(int i = head[u]; i != -1; i = edge[i].next) 58 { 59 int v = edge[i].v; 60 indeg[v]--; 61 if(indeg[v] == 0) //此时这个人不需要比其他人的银子多了 62 { 63 q.push(v); 64 money.push(temp+1); //依题意,银子总数最少 65 } 66 } 67 } 68 // if(k < n)return -1; //存在有向环,总之不能进行拓扑排序 69 // if(res) return 0; //可以进行拓扑排序,并且只有唯一一种方式,seq数组即是排序完好的序列 70 // return 1; ////可以进行拓扑排序,有多种情况,seq数组是其中一种序列 71 if(k < n) printf("Unhappy!\n"); 72 else printf("%d\n",ans); 73 74 return 0; 75 } 76 int main() 77 { 78 int a,b; 79 while(~scanf("%d %d",&n,&m)) 80 { 81 init(); 82 for(int i = 1; i<= m; i++) 83 { 84 scanf("%d %d",&a,&b); 85 addedge(b,a); 86 indegree[a]++;//入度越多 说明分的钱越多 87 } 88 topo(); 89 } 90 return 0; 91 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:HDU 3078 Network
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 排序汇总 2020-05-05
- 二叉排序树 2020-05-02
- 排序算法之快速排序代码c++ 2020-04-01
- tmp 2020-04-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash