虎威山上的分配

作者: 关于计算机  发布:2019-09-25

历年过大年的时候,座山雕都会给兄弟们分银子,分银子在此之前,座山雕允许大伙儿发表意见,因为假使没办法满意全部人的视角,指不定何人要搞出什么样大新闻。但是每个人在提意见的时候只得说:“作者认为A 分的银子应该比 B 多!”。座山雕决定要寻觅一种分配方案,满足全体人的意见,同不日常间使得全体人分得的银子总的数量最少,何况每一个人力争的银两最少为 100 两。

输入格式

第一行七个整数 n,m(0<n≤一千0,0<m≤30000),表示总人数和总意见数;

以下 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("%dn",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 }

 

本文由王中王开奖结果发布于关于计算机,转载请注明出处:虎威山上的分配

关键词:

上一篇:常用关键字列表集合
下一篇:没有了