ACdream 1089 barty的智商（二分）

骑猪看日落 2022-06-14 12:21 174阅读 0赞

题目链接：  
[ACdream 1089][]

题解：  
二分。  
直接二分枚举智商，然后将大于二分出来的智商的边抠出来建一个图，然后直接从入度为 0<script type="math/tex" id="MathJax-Element-7">0</script> 的点开始搜。  
低于或等于当前智商的课程肯定能直接学习，大于的就看一下能不能从先修课那里转过来。  
如果能搜到全部点（课程），那么肯定能学完的。依次二分得到最低智商即可。

AC代码：

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e6+10;
    vector<int>G[12345];
    int in[12345]; //入度 
    int x[12345],y[12345],w[12345];
    int n,m;
    bool check(int zhishang)
    {
        for(int i=0;i<n;i++){
            G[i].clear();
            in[i] = 0;
        }
        for(int i = 0; i < m ; i++)
        {
            int a = x[i] - 1;
            int b = y[i] - 1;
            int c = w[i];
            if(c > zhishang )
            {
                G[b].push_back(a);
                in[a]++;
            }
        }
        queue<int>q;
        for(int i=0;i<n;i++){
            if(in[i]==0){
                q.push(i);
            }
        }
        int cnt = 0;
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            cnt++;
            for(int i = 0; i< G[u].size();i++)
            {
                int v = G[u][i];
                in[v]--;
                if(in[v] == 0){ q.push(v);}
            }
        }
        if(cnt==n)return true;
        else return false;
    }
    int main()
    {   
        int t ;
        cin>>t;
        while(t--)
        {
            cin>>n>>m;
            for(int i=0;i<m;i++){
                cin>>x[i]>>y[i]>>w[i];
            }
            int l=0;
            int r=1e9;
            int mid;
        //  while(l < r)//二分智商 //332ms
            for(int i=1;i<=100;i++) //964ms 
            {
                int mid = (l+r)>>1;
                if(check(mid)){
                    r = mid;
                }
                else{
                    l = mid + 1;
                }
            }
            cout<<l<<endl;
        }
        return 0;
    }

[ACdream 1089]: http://acdream.info/problem?pid=1089