计蒜客 | 拓扑排序 | 虎威山上的分配

2018-06-17 21:37:43来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

每年过年的时候,座山雕都会给兄弟们分银子,分银子之前,座山雕允许大伙儿发表意见,因为要是没法满足所有人的意见,指不定谁要搞出什么大新闻。不过每个人在提意见的时候只能说:“我认为 A 分的银子应该比 B 多!”。座山雕决定要找出一种分配方案,满足所有人的意见,同时使得所有人分得的银子总数最少,并且每个人分得的银子最少为 100 两。

输入格式

第一行两个整数 n,m(0<n10000,0<m20000),表示总人数和总意见数;

以下 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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【DTOJ】1001:长方形周长和面积

下一篇:HDU 3078 Network