H - Subway Pursuit CodeForces - 1039B

题意：n个点m条边的有向图中，需要反向一些边使得图中无环。求这些需要反向的边中最小的边权值及需要反向的边的序号。

题解：不断二分答案然后判断是否有环，如果无环则增大答案，否则减小答案。判断是否有环可以用拓扑排序。在拓扑排序的过程中可以根据边的拓扑序来判断该边是否需要反转。对于边权值小于mid的边，由于这种边的方向是任意的，所以对于判断图是否有环不影响，拓扑排序的时候不需要加入这种边。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n,m,tot,num,du[maxn],rak[maxn];
vector<int>ed[maxn];                   //拓扑排序的边集
vector<int>ans;                        //反向的边集
struct edge
{
    int u,v,w;
}edg[maxn];
void topsort()
{
    tot = 0;
    queue<int>Q;
    for(int i = 1;i <= n;i++)
    {
        if(du[i] == 0)
        {
            rak[i] = ++tot;
            Q.push(i);
        }
    }
    while(!Q.empty())
    {
        int i = Q.front();
        Q.pop();
        for(int j = 0;j < ed[i].size();j++)
        {
            du[ed[i][j]]--;
            if(du[ed[i][j]] == 0)
            {
                rak[ed[i][j]] = ++tot;
                Q.push(ed[i][j]);
            }
        }
    }
}
bool OK(int mid)
{
    memset(du,0,sizeof(du));
    for(int i = 0;i < maxn;i++) ed[i].clear();
    for(int i = 1;i <= m;i++)
    {
        if(edg[i].w > mid)
        {
            ed[edg[i].u].push_back(edg[i].v);
            du[edg[i].v]++;
        }
    }
    topsort();
    for(int i = 1;i <= n;i++)
    {
        if(du[i] > 0) return false;      //判断是否有环
    }
    ans.clear();
    for(int i = 1;i <= m;i++)
    {
        if(edg[i].w <= mid && rak[edg[i].u] > rak[edg[i].v])  //如果边的拓扑序与原来相反则这个边需要反向
        {
            ans.push_back(i);
        }
    }
    return true;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%d %d %d",&edg[i].u,&edg[i].v,&edg[i].w);
    }
    int l = 0,r = 1e9,mid;
    while(l <= r)
    {
        mid = (l + r) / 2;
        if(OK(mid))
        {
            num = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%d %d\n",num,ans.size());
    for(int i = 0;i < ans.size();i++)
    {
        printf("%d ",ans[i]);
    }
    printf("\n");
    return 0;
}

H - Subway Pursuit CodeForces - 1039B

题意：在一[1,n]内查找一个点，每次可以询问该点是否在区间内，返回YES或者NO。每次询问后该点会移动0~k步。最多询问4500次，要求找到这个点。

题解：不断二分区间，每次在区间内随机选择一个数询问。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,flag;
string s;
bool OK(ll l,ll r)
{
    printf("%lld %lld\n",l,r);
    cin>>s;
    if(s[0] == 'N') return false;
    else if(s[0] == 'Y')
    {
        if(l == r) flag = 1;
        return true;
    }
}
int main()
{
    srand(time(NULL));
    cin>>n>>k;
    ll l,r,mid;
    l = 1,r = n;
    while(1)
    {
        mid = (l + r) / 2;
        if(OK(l,mid))
        {
            r = mid;
            if(flag) break;
        }
        else
        {
            l = mid + 1;
        }
        l = max((ll)1,l - k);
        r = min(n,r + k);
        mid = rand() % (r - l + 1) + l;
        OK(mid,mid);
        if(flag) break;
        l = max((ll)1,l - k);
        r = min(n,r + k);
    }
    return 0;
}