【【henuacm2016级暑期训练】动态规划专题 O】Robot Rapping Results Report

【链接】 我是链接,点我呀:)

【题意】

让你确定一个最小的k
使得1..k这些比赛的结果能够推导出所有人之间的实力大小

【题解】

如果关系越多。那么就越能确定所有人之间的大小关系。
(多一点也能唯一确定。不嫌多
那么就二分一下k.
做一个拓扑排序。
如果能做唯一的拓扑排序。那么就ok
否则返回false.

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int M = 1e5;

int n,m,ru[M+10];

vector<pair<int,int> > g[M+10];

pair<int,int> a[M+10];

queue<int> dl;

bool ok(int mid){

    memset(ru,0,sizeof ru);

    for (int i = 1;i <= mid;i++){

        ru[a[i].second]++;

    }

    int cnt = 0;

    while (!dl.empty()) dl.pop();

    for (int i = 1;i <= n;i++)

        if (ru[i]==0){

            dl.push(i);

        }

    while (!dl.empty()){

        int x = dl.front();dl.pop();

        cnt++;

        if (!dl.empty()) return false;

        for (auto y:g[x]){

            if (y.second>mid) continue;

            ru[y.first]--;

            if (ru[y.first]==0) dl.push(y.first);

        }

    }

    if (cnt==n) return true;

    return false;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m;

    for (int i = 1;i <= m;i++){

        int x,y;

        cin >> x >> y;

        a[i] = {x,y};

        g[x].push_back({y,i});

    }

    int l = 1,r = m,temp = -1;

    while (l<=r){

        int mid = (l+r)>>1;

        if (ok(mid)){

            r = mid - 1;temp = mid;

        }else{

            l = mid + 1;

        }

    }

    cout<<temp<<endl;

	return 0;

}