abc139_E

abc139_E

题意简述：

\(n\) 个人进行 \(n(n -1)/2\) 场比赛，每个人都要以一个特定的顺序与其他人比赛，

且每个人每天只可以比一场比赛，问最少比赛的天数为多少，无解输出 \(-1\)

正解 :

发现一个人假如可以和另外一个打比赛时，和他打比赛肯定是最优的

因为另外那个人此时肯定也只可以和他打比赛，对除了这两人之外的其他人没有影响

每一场比赛都可以用一个二元组表示 \((x, y)\) 成一个节点，节点向节点连边表示限制

比如说第一个人要先后和第二个人和第三个人打比赛

那么 \((1, 2) \to (1,3)\)

这样的话只有入度为 \(0\) 的点（比赛）才可以进行，用 \(topo\) 排序做一下

有环的话肯定无解，没环的话答案就是最长链

前一个很好证明，关键是后面一个怎么证明

其实也挺好证，因为当前入度为 \(0\) 的节点（比赛）肯定都可以在同一天进行完

具体一点 ：\((1,2) 和 (1,3)\) 肯定不会同时可以进行比赛（同时入度为 \(0\)）

Code :

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#define N 1003

using namespace std;

struct edge{
    int to, nxt;
}e[N * N * 3];

int n, cnt;
int ins[N * N], mp[N][N], fir[N * N], t[N * N];

queue < int > Q;

int id(int ,int);
void add(int ,int);

int main(){
    scanf("%d", &n); int ans = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < n; ++j)
            scanf("%d", mp[i] + j);
    for(int i = 1; i <= n; ++i)
        for(int j = 2; j < n; ++j)
            add(id(i, mp[i][j - 1]), id(i, mp[i][j]));
    for(int i = 1; i <= n * n; ++i){
        if(!ins[i]) Q.push(i);
        t[i] = 1;
    }
    while(!Q.empty()){
        int u = Q.front(); Q.pop(); ans = max(ans, t[u]);
        for(int i = fir[u]; i; i = e[i].nxt){
            int v = e[i].to;
            --ins[v];
            if(!ins[v])
                Q.push(v), t[v] = t[u] + 1;
        }
    }
    for(int i = 1; i <= n * n; ++i) 
        if(ins[i]) ans = -1;
    cout << ans << endl;
    return 0;
}

int id(int x,int y){
    if(x > y) swap(x, y);
    return (x - 1) * n + y;
}

void add(int u,int v){
    e[++cnt] = (edge){v, fir[u]}; fir[u] = cnt; ++ins[v];
    return ;
}

收藏

喜欢 0