首页 > 代码库 > SHU 第15届上海大学程序设计联赛夏季赛[热身赛] 第三题(G题) - 英语成绩

SHU 第15届上海大学程序设计联赛夏季赛[热身赛] 第三题(G题) - 英语成绩

2024-10-20 00:29:39   210人阅读

技术分享

技术分享

 

看完题目就觉得是个图论题……

每个人的成绩就是vertice，两个人的分数差就是edge，那么肯定类似于一种relax的方式，不断将每个人的成绩的min往上提，

当然，单纯的遍历一遍G.E肯定不可能就得到yaoge成绩min的最大值，所以直觉上就想到了bellman-ford，写了一发交了就过了

 1 #include<cstdio>
 2 int n,p,q;
 3 int score[105];
 4 struct Edge{
 5     int high,low,delta;
 6 }edge[1005];
 7 void relax(int low,int high,int delta)
 8 {
 9     if(score[low]+delta>score[high]) score[high]=score[low]+delta;
10 }
11 int main()
12 {
13     int t;
14     scanf("%d",&t);
15     while(t--)
16     {
17         scanf("%d%d%d",&n,&p,&q);
18         for(int i=1;i<=n;i++) score[i]=0;
19         for(int i=1;i<=p;i++)
20         {
21             int id,min;
22             scanf("%d%d",&id,&min);
23             if(min>score[id]) score[id]=min;
24         }
25         for(int i=1;i<=q;i++)
26         {
27             scanf("%d%d%d",&edge[i].high,&edge[i].low,&edge[i].delta);
28         }
29         for(int k=1;k<=n;k++)
30         {
31             for(int i=1;i<=q;i++)
32             {
33                 relax(edge[i].low,edge[i].high,edge[i].delta);
34             }
35         }
36         printf("%d\n",score[1]);
37     }
38 }

还是比较惊喜的……不过写完听说这是个叫做“拆分约束系统”的东西，去看了一下发现差不多就是这么回事儿，看来我的直觉还挺准的（笑哭）……

SHU 第15届上海大学程序设计联赛夏季赛[热身赛] 第三题(G题) - 英语成绩


联系
我们