• 图论刷题记录

    [NOIP2003 提高组] 神经网络 - 洛谷P1038 [NOIP2003 提高组] 神经网络

    容鄙人说一下，这是鄙人刷过最caodan的一个题，我就没见过这么刁钻的数据..

    传入层的出度可以是0，但是，他依然可以传导，并且还应该被当做答案输出

    第二，传入层一开始就是激发状态！并且不能减u  我就没见过这么caodan的

    题目似乎也说了

     意思是传入层根本没有j属于i,那么按这个推ci就是负数，也就无法传导，所以...就很离谱的不要减u才正确，关键是题目根本没有挑明。。

    1. # include <iostream>
    2. # include<vector>
    3. # include<queue>
    4.  
    5. using namespace std;
    6.  
    7. int ru[110];
    8. int chu[110];
    9.  
    10. int f[110][110];
    11.  
    12. vector<int>v[110];
    13.  
    14. int c[110],u[110];
    15. queue<int>q;
    16. int main()
    17. {
    18.     int n,m;
    19.  
    20.     cin>>n>>m;
    22.     for(int i=1; i<=n; i++)
    23.     {
    24.        cin>>c[i]>>u[i];
    25.        
    26.       
    27.     }
    28.  
    29.     for(int i=1; i<=m; i++)
    30.     {
    31.         int x,y,z;
    32.  
    33.         cin>>x>>y>>z;
    35.         f[x][y]=z;
    36.  
    37.         v[x].push_back(y);
    38.  
    39.         chu[x]++;
    40.  
    41.         ru[y]++;
    42.  
    43.  
    44.     }
    45.  
    46.     for(int i=1; i<=n; i++)
    47.     {
    48.         if(ru[i]==0)
    49.         {
    50.             q.push(i);
    51.  
    52.             c[i]-=u[i];
    53.         }
    54.         else
    55.         {
    56.             c[i]-=u[i];
    57.  
    58.         }
    59.     }
    60.  
    61.  
    62.     while(!q.empty())
    63.     {
    64.         int now=q.front();
    65.  
    66.         q.pop();
    67.  
    68.         for(auto it:v[now])
    69.         {
    70.  
    71.             ru[it]--;
    72.  
    73.             c[it]+=c[now]*f[now][it];
    74.  
    75.             if(ru[it]==0&&c[it]>0)
    76.             {
    77.                 q.push(it);
    78.             }
    79.         }
    80.     }
    81.     int flag=0;
    82.  
    83.     for(int i=1; i<=n; i++)
    84.     {
    85.         if(chu[i]==0&&c[i]>0)
    86.         {
    87.             cout<<i<<" "<<c[i]<<endl;
    88.  
    89.             flag=1;
    90.         }
    91.     }
    92.  
    93.     if(!flag)
    94.     {
    95.         cout<<"NULL";
    96.  
    97.  
    98.     }
    99.  
    100.  
    101.     return 0;
    102. }
    [NOIP2013]车站分级

    把等级低的往等级高的连一条有向边即可，拓扑DP

    1. #include <iostream>
    2. # include<algorithm>
    3. # include<cstring>
    4. # include<vector>
    5. # include<queue>
    6.  
    7.  
    8. using namespace std;
    9.  
    10. typedef long long int ll;
    11.  
    12. int du[1010];
    13.  
    14. int st[1010];
    15.  
    16. bool book[1010];
    17.  
    18. bool edge[1010][1010];
    19.  
    20. vector<int>v[1010];
    21.  
    22. int ans[1010];
    23.  
    24. int dp[1010];
    25.  
    26. queue<int>q;
    27. int main()
    28. {
    29.     int n,m;
    30.  
    31.     cin>>n>>m;
    33.     while(m--)
    34.     {
    35.         int t;
    36.  
    37.         cin>>t;
    39.  
    40.         for(int i=1; i<=t; i++)
    41.         {
    42.             cin>>st[i];
    44.             book[st[i]]=1;
    45.         }
    46.  
    47.  
    48.         for(int i=st[1]; i<=st[t]; i++)
    49.         {
    50.             if(!book[i])
    51.             {
    52.                 for(int j=1; j<=t; j++)
    53.                 {
    54.                     if(!edge[i][st[j]])
    55.                     {
    56.  
    57.                         edge[i][st[j]]=1;
    58.  
    59.  
    60.                         v[i].push_back(st[j]);
    61.  
    62.                         du[st[j]]++;
    63.  
    64.                     }
    65.                 }
    66.             }
    67.         }
    68.  
    69.         memset(book,0,sizeof(book));
    70.  
    71.  
    72.     }
    73.  
    74.  
    75.     for(int i=1; i<=n; i++)
    76.     {
    77.         if(!du[i])
    78.         {
    79.             q.push(i);
    80.  
    81.             dp[i]=1;
    82.         }
    83.     }
    84.     int ans=1;
    85.  
    86.     while(!q.empty())
    87.     {
    88.         int now=q.front();
    89.  
    90.         q.pop();
    91.  
    92.         for(auto it:v[now])
    93.         {
    94.             du[it]--;
    95.             if(du[it]==0)
    96.                 q.push(it);
    97.  
    98.             if(!dp[it])
    99.                 dp[it]=dp[now]+1;
    100.             else
    101.                 dp[it]=max(dp[it],dp[now]+1);
    102.  
    103.             ans=max(ans,dp[it]);
    104.         }
    105.     }
    106.  
    107.     cout<<ans;
    108.     return 0;
    109. }
    [HNOI2015]菜肴制作

    两种贪心方法，第一种是放进小根堆，把最小的先输出。但会被hack，例如

    （5,2）  （4,3）  输出  1 4 3 5 2 实际上应该是   1 5 2 4 3。

    第二种就是放进大根堆，建立反图，倒着输出

    (5,2) (4,3)      ->  (2,5)  (3,4) ->  3 4 2 5 1   -> 1 5 2 4 3 

    这样就OK了

    1. # include <iostream>
    2. # include<algorithm>
    3. # include<cstring>
    4. # include<vector>
    5. # include<queue>
    6.  
    7. using namespace std;
    8. typedef long long int ll;
    9.  
    10. vector<int>v[100000+10];
    11. int du[100000+10];
    12. priority_queue<int>q;
    13. int ans[100000+10];
    14. int main()
    15. {
    16.  
    17.  
    18.       int t;
    19.  
    20.       cin>>t;
    22.       while(t--)
    23.       {
    24.           int n,m,len;
    25.  
    26.           cin>>n>>m;
    28.           while(!q.empty())
    29.             q.pop();
    30.  
    31.           for(int i=1;i<=n;i++)
    32.           {
    33.               v[i].clear();
    34.  
    35.               du[i]=0;
    36.           }
    37.  
    38.           for(int i=1;i<=m;i++)
    39.           {
    40.               int x,y;
    41.  
    42.               cin>>x>>y;
    44.               v[y].push_back(x);
    45.  
    46.               du[x]++;
    47.  
    48.           }
    49.           
    50.           for(int i=1;i<=n;i++)
    51.           {
    52.               if(du[i]==0)
    53.                 q.push(i);
    54.           }
    55.           len=0;
    56.           
    57.           while(!q.empty())
    58.           {
    59.               int now=q.top();
    60.               len++;
    61.               ans[len]=now;
    62.               q.pop();
    63.               
    64.               for(auto it:v[now])
    65.               {
    66.                   du[it]--;
    67.                   
    68.                   if(!du[it])
    69.                     q.push(it);
    70.               }
    71.           }
    72.           
    73.           if(len!=n)
    74.           {
    75.               cout<<"Impossible!"<<endl;
    76.               continue;
    77.           }
    78.           for(int i=len;i>=1;i--)
    79.           {
    80.               cout<<ans[i]<<" ";
    81.           }
    82.  
    83.           cout<<endl;
    84.       }
    85.  
    86.     return 0;
    87. }
    迷宫2

    基于迪杰斯特拉的BFS，为了能够拦截，必须上下左右连续建造墙，从第一整列，第n整行开始扩展，每次选取最小花费的点，只能上下左右移动，一旦到达第一行或者第m列，拦截成功。细节较多，要开ll

    1. #include <queue>
    2. #include <iostream>
    3. #include <algorithm>
    4. #include <cstdio>
    5. #include <cstring>
    6.  
    7. using namespace std;
    8. typedef long long ll;
    9.  
    10. int nx[4]= {0,0,-1,1};
    11. int ny[4]= {1,-1,0,0};
    12. int n,m;
    13. bool check(int x,int y)
    14. {
    15.     return (x>=1&&x<=n&&y>=1&&y<=m);
    16. }
    17. ll mp[510][510], rem[510][510], inf=1e18,edge[510][510];
    18. struct node
    19. {
    20.     int x,y;
    21.  
    22.     ll cost;
    23.     friend bool operator<(node a, node b)
    24.     {
    25.         return a.cost>b.cost;
    26.     }
    27. };
    28. priority_queue<node>q;
    29. bool book[510][510];
    30. int main ()
    31. {
    32.  
    33.     int t;
    34.  
    35.     cin>>t>>n>>m;
    36.     while(t--)
    37.     {
    38.         
    39.         for(int i=1; i<=n; i++)
    40.         {
    41.             for(int j=1; j<=m; j++)
    42.             {
    43.                 cin>>mp[i][j];
    45.                 if(mp[i][j]==0)
    46.                     mp[i][j]=-1;
    47.  
    48.                 else if(mp[i][j]==-1)
    49.                     mp[i][j]=0;
    50.  
    51.                 rem[i][j]=inf;
    52.             }
    53.         }
    54.  
    55.         memset(book,0,sizeof(book));
    56.  
    57.         for(int i=1; i<=n; i++)
    58.         {
    59.             if(mp[i][1]==-1)
    60.                 continue;
    61.  
    62.             struct node now;
    63.  
    64.             now.x=i;
    65.             now.y=1;
    66.  
    67.             if(mp[i][1]==0)
    68.             {
    69.                 now.cost=0;
    70.                 rem[i][1]=0;
    71.                 book[i][1]=1;
    72.             }
    73.             else
    74.             {
    75.                 now.cost=mp[i][1];
    76.                 rem[i][1]=now.cost;
    77.                 book[i][1]=1;
    78.             }
    79.             q.push(now);
    80.  
    81.         }
    82.  
    83.  
    84.         for(int i=1; i<=m; i++)
    85.         {
    86.             if(mp[n][i]==-1)
    87.                 continue;
    88.  
    89.             struct node now;
    90.  
    91.             now.x=n;
    92.             now.y=i;
    93.             if(mp[n][i]==0)
    94.             {
    95.                 now.cost=0;
    96.                 rem[n][i]=0;
    97.                 book[n][i]=1;
    98.             }
    99.             else
    100.             {
    101.                 now.cost=mp[n][i];
    102.                 rem[n][i]=now.cost;
    103.                 book[n][i]=1;
    104.             }
    105.  
    106.             q.push(now);
    107.  
    108.         }
    109.  
    110.  
    111.         ll ans=-1;
    112.  
    113.         while(!q.empty())
    114.         {
    115.             struct node now=q.top();
    116.             q.pop();
    117.  
    118.             if(now.x==1||now.y==m)
    119.             {
    120.                 ans=now.cost;
    121.                 break;
    122.             }
    123.  
    124.             for(int i=0; i<4; i++)
    125.             {
    126.                 int xx=now.x+nx[i];
    127.                 int yy=now.y+ny[i];
    128.                 if(!check(xx,yy))
    129.                     continue;
    130.  
    131.                 if(mp[xx][yy]==-1)
    132.                     continue;
    133.                 if(rem[xx][yy]>now.cost+mp[xx][yy])
    134.                 {
    135.  
    136.                     rem[xx][yy]=now.cost+mp[xx][yy];
    137.                     struct node tail;
    138.                     book[xx][yy]=1;
    139.                     tail.x=xx;
    140.                     tail.y=yy;
    141.                     tail.cost=rem[xx][yy];
    142.                     q.push(tail);
    143.  
    144.                 }
    145.             }
    146.         }
    147.  
    148.         while(!q.empty())
    149.             q.pop();
    150.  
    151.         cout<<ans<<endl;
    152.  
    153.  
    154.     }
    155.  
    156. }

  • 相关阅读:
    轻量级RPC分布式网络通信框架设计——序列化协议Protobuf
    实现动态表单的一种思路 | 京东云技术团队
    互联网加竞赛 车道线检测(自动驾驶 机器视觉)
    【黑马程序员JVM学习笔记】02.内存结构
    应用系统设计：基于Spring security设计一套安全认证和授权的服务
    视频融合云平台EasyCVR增加多级分组，可灵活管理接入设备
    2023湖南省赛-B Square game
    抓包与发流软件与网络诊断
    three.js学习笔记(十九)——后期处理
    设计模式-面试题
  • 原文地址：https://blog.csdn.net/jisuanji2606414/article/details/126112038